Problem

A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children. In other words, every node must have 0 or 2 children.

Check if a tree is a full binary tree

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input: root = [1, 2, 3, 4, 5, null, null]
Output: true
Exmplanation:
       1
      / \
     2   3
    / \
   4   5
This is a full binary tree as every node other than the leaves has two children.

Example 2:

1
2
3
4
5
6
7
8
9

Input: root = [1, 2, 3, 4, null, null, 5]
Output: false
Explanation:
       1
      / \
     2   3
    /     \
   4       5
This is not a full binary tree as the node with value 2 has only one child.

We have seen full binary tree here: Full Binary Tree#Definition.

Solution

Method 1 - Using DFS

We can run the dfs and consider the cases:

  • If the tree is empty (root is null), it is considered a full binary tree.
  • Traverse the tree recursively (using DFS).
  • Check the number of children for each node: it must be 0 or 2.
  • If all nodes satisfy the condition, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class Solution {
    public boolean isFullBinaryTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if ((root.left == null && root.right != null) || (root.left != null && root.right == null)) {
            return false;
        }
        return isFullBinaryTree(root.left) && isFullBinaryTree(root.right);
    }
}
1
2
3
4
5
6
7

class Solution:
    def isFullBinaryTree(self, root: Optional['Solution.TreeNode']) -> bool:
        if root is None:
            return True
        if (root.left is None and root.right is not None) or (root.left is not None and root.right is None):
            return False
        return self.isFullBinaryTree(root.left) and self.isFullBinaryTree(root.right)

Complexity

  • ⏰ Time complexity:  O(n), where n is the number of nodes in the tree since we need to visit each node once.
  • 🧺 Space complexity: O(h), where h is the height of the tree. In the worst case (a skewed tree), the recursive stack will store all nodes in one path, resulting in O(n) space complexity.