Problem

The problem is to find all the full nodes in a binary tree. A full node in a binary tree is defined as a node that has both left and right children present. We need to return or print all such nodes.

Examples

Example 1

1
2
3
4
5
6
7
8
9

 Input:
 Binary Tree:
      1
     / \
    2   3
   / \
  4   5
 Output: [1, 2]
 Explanation: Node 1 has both children (2 and 3), and Node 2 has both children (4 and 5). Hence, they are full nodes

Example 2

1
2
3
4
5
6
7
8
9

Input:
Binary Tree:
     10
    /  \
   20   30
      /    \
     40    50
Output: [10, 30]
Explanation: Node 10 has both children (20 and 30), and Node 30 has both children (40 and 50). Hence, they are full nodes.

Example 3

1
2
3
4
5
6
7

Input:
Binary Tree:
     5
    / \
   8   12
Output: [5]
Explanation: Node 5 has both children (8 and 12). Hence, it is the only full node.

Solution

Method 1 - DFS

The intuition behind the problem lies in understanding what constitutes a “full node.” To determine whether a node is a full node:

  1. Check if the left child is present.
  2. Check if the right child is present.

This can be achieved using traversal techniques such as pre-order, in-order, or post-order. During the traversal, we check the condition for each node and add it to the result if it qualifies as a full node.

Approach

The approach involves recursively traversing the binary tree and checking whether a node has both left and right children:

  1. Start from the root node and traverse the tree using Depth-First Search (DFS).
  2. For each node, check if both its left and right children are not null.
  3. If true, it is a full node; add it to the result list.
  4. Return or print all nodes collected in the result list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public List<Integer> findFullNodes(TreeNode root) {
        List<Integer> fullNodes = new ArrayList<>();
        findFullNodesHelper(root, fullNodes);
        return fullNodes;
    }

    private void findFullNodesHelper(TreeNode node, List<Integer> fullNodes) {
        if (node == null) {
            return;
        }
        // Check if it is a full node
        if (node.left != null && node.right != null) {
            fullNodes.add(node.val);
        }
        // Recursive calls for left and right children
        findFullNodesHelper(node.left, fullNodes);
        findFullNodesHelper(node.right, fullNodes);
    }
    
    // Main function to test the code
    public static void main(String[] args) {
        // Example Tree: 1 -> [2, 3] -> [4, 5]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println(solution.findFullNodes(root)); // Output: [1, 2]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def findFullNodes(self, root):
        full_nodes = []
        self._find_full_nodes_helper(root, full_nodes)
        return full_nodes

    def _find_full_nodes_helper(self, node, full_nodes):
        if not node:
            return
        # Check if it is a full node
        if node.left and node.right:
            full_nodes.append(node.val)
        # Recursive calls for left and right children
        self._find_full_nodes_helper(node.left, full_nodes)
        self._find_full_nodes_helper(node.right, full_nodes)

# Main function to test the code
if __name__ == "__main__":
    # Example Tree: 1 -> [2, 3] -> [4, 5]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    solution = Solution()
    print(solution.findFullNodes(root))  # Output: [1, 2]

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)

Method 2 -

Code

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)

Objective: Given a binary tree, print all nodes will are full nodes.

Full Nodes: Nodes Which has both the children, left and right are called Full Nodes Approach: quite simple Solution. Do the any of the traversal (inorder, preorder, postorder etc). During traversal, check the node if it has left child and right child, If yes then print it Complete Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public void FindFullNodes(Node root) {
 // do the traversal and print all the nodes which has left and right
 // child
 if (root != null) {
 FindFullNodes(root.left);
 if (root.left != null && root.right != null) {
 System.out.print(root.data + " ");
 }
 FindFullNodes(root.right);
 }
}