Domain 2MediumMEDIUM

Check Completeness of a Binary Tree

Uses BFS to traverse nodes level-by-level; returns False immediately upon encountering a non-null node after a null child in the queue traversal sequence.

Domain: medium•Updated: 2026-09-05
#Level Order Traversal#Queue (Deque)#O(N) Time Complexity

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:

  1. Every level, except possibly the last one, is completely filled.
  2. 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 None in level-order traversal followed later by a non-None node 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 O(N2)O(N^2) 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 be None.
  • 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).

  1. If we pop a None, set found_gap = True.
  2. If we pop a valid node and found_gap is already True, return False.

Approach

  1. Initialize a queue with the root (if not None) and a flag found_gap = False.
  2. While the queue is not empty, pop the front element (curr).
  3. If curr is None:
    • 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.
  4. If curr is not None:
    • Check the flag: If found_gap is already True, it means we found a valid node after an empty spot in level-order sequence -> Return False.
    • Add curr.left and curr.right to the queue. Note that even if these are None, they must be added so they can trigger the gap detection logic later (or simply finish processing).
  5. If loop completes without returning False, return True.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes in the tree. We visit every node exactly once using BFS.
  • Space Complexity: O(W)O(W) where WW 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 O(N/2)O(N/2).

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 (root is None): The function returns True immediately, 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 sets found_gap=True. Subsequently, when any actual node exists to the right of the gap is popped later -> found_gap check 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).