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(n), where n is the number of nodes in the binary tree.. Each node is visited exactly once during the traversal.
  • 🧺 Space complexity: O(n), where h is the height of the tree (due to the recursion stack).
    • In the worst case (skewed tree), h = n, so space is O(n).
    • The result list can also take up to O(n) space in the worst case (if all nodes are full nodes), but typically O(n) overall.