Problem Breakdown
We are given the root of a binary tree and must determine if it is a Complete Binary Tree (CBT). A CBT satisfies two conditions:
- Every level, except possibly the last one, is completely filled.
- All nodes in the last level are as far left as possible.
Inputs: The root node of a binary tree (TreeNode).
Outputs: Boolean value indicating completeness.
Implicit Constraints & Edge Cases:
- Empty Tree: Robust logic handles an empty input gracefully (usually considered complete).
- Single Node: Trivially satisfies the CBT definition.
- Gaps on the Right: The critical failure case is encountering a
Nonein level-order traversal followed later by a non-Nonenode at the same depth or deeper levels.
Intuition
A brute-force approach might try to validate each subtree recursively for “fullness” or calculate heights of every node, leading to complexity due to repeated traversals.
Key Insight: A Complete Binary Tree corresponds exactly to a contiguous array representation (like a binary heap). If you traverse the tree level-by-level from left-to-right using BFS:
- Once you encounter an empty spot (
None), all subsequent nodes in your traversal sequence must also beNone. - This is because any valid node appearing after a gap would imply that index was skipped, violating contiguity.
Optimal Approach: Perform BFS using a queue. Maintain a boolean flag indicating if we have seen the first empty spot (found_gap).
- If we pop a
None, setfound_gap = True. - If we pop a valid node and
found_gapis alreadyTrue, returnFalse.
Approach
- Initialize a queue with the root (if not None) and a flag
found_gap = False. - While the queue is not empty, pop the front element (
curr). - If
currisNone:- Set
found_gap = True. This marks that we have reached an empty spot in level-order traversal. We continue processing to check if any non-null nodes appear later (which would be invalid). Do not add children for a null node as they don’t exist structurally.
- Set
- If
curris notNone:- Check the flag: If
found_gapis already True, it means we found a valid node after an empty spot in level-order sequence -> ReturnFalse. - Add
curr.leftandcurr.rightto the queue. Note that even if these areNone, they must be added so they can trigger the gap detection logic later (or simply finish processing).
- Check the flag: If
- If loop completes without returning False, return
True.
Complexity Analysis
- Time Complexity: where is the number of nodes in the tree. We visit every node exactly once using BFS.
- Space Complexity: where is the maximum width (number of nodes at any level) of the binary tree, due to queue storage. In a balanced complete tree, this approaches .
Solution
from collections import deque
# Assuming standard LeetCode TreeNode structure: class TreeNode(val=0, left=None, right=None): pass
def isCompleteTree(root):
if not root:
return True
queue = deque([root])
found_gap = False
while queue:
curr = queue.popleft()
# If we encounter a null node in level-order traversal,
# all subsequent nodes must also be null.
if curr is None:
found_gap = True
continue
# If we have already seen a gap (null) and now find a valid node,
# the tree is not complete because there's an empty spot before this one.
if found_gap:
return False
# Add children to queue regardless of whether they are None or TreeNode.
# This ensures we detect gaps in subsequent levels correctly.
left_child = curr.left
right_child = curr.right
queue.append(left_child)
queue.append(right_child)
return True
Edge Cases Handled
- Empty Tree (
rootis None): The function returnsTrueimmediately, consistent with the definition that an empty tree satisfies completeness. - Single Node: Queue processes root, adds two nulls to queue, then pops nulls setting flag but no non-null nodes follow -> Returns
True. - Last Level Gaps on Right (Example 2): The BFS encounters a valid node in the last level after processing its left sibling’s missing child. When popping that right-side gap (
None), it setsfound_gap=True. Subsequently, when any actual node exists to the right of the gap is popped later ->found_gapcheck returns False immediately. - Skewed Trees: A tree with only left children or right children will be processed correctly; gaps on the “missing” side trigger the flag appropriately if they appear before valid nodes of deeper levels (which shouldn’t happen for a complete tree, but logic handles it).