958. Check Completeness of a Binary Tree - Explanation

Description

You are given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and (2^h)^ nodes inclusive at the last level h`.

Example 1:

Input: root = [1,2,3,4,5,6]

Output: true

Example 2:

Input: root = [1,2,3,4,5,null,7]

Output: false

Example 3:

Input: root = [1,2,3,4]

Output: true

Constraints:

1 <= The number of nodes in the tree <= 100.
1 <= Node.val <= 1000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Breadth First Search

Intuition

In a complete binary tree, all nodes are as far left as possible, with no gaps. If we traverse level by level and encounter a null node, all subsequent nodes in the traversal must also be null. If we find any non-null node after a null, the tree is not complete.

Algorithm

Initialize a queue with the root node.
Process nodes in BFS order:
- Dequeue a node and add its left and right children (even if null) to the queue.
- If the dequeued node is null, drain the remaining queue.
- If any non-null node appears after a null, return false.
Return true if the entire queue is processed without finding a non-null after null.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        q = deque([root])
        while q:
            node = q.popleft()
            if node:
                q.append(node.left)
                q.append(node.right)
            else:
                while q:
                    if q.popleft():
                        return False
        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search (Optimal)

Intuition

This is a cleaner version of the BFS approach. Instead of draining the queue after seeing null, we use a flag to track whether a null has been seen. If we encounter a non-null node after the flag is set, the tree is incomplete.

Algorithm

Initialize a queue with the root and a boolean flag nullSeen = false.
Process each node from the queue:
- If the node is non-null and nullSeen is true, return false.
- If the node is non-null, add both children to the queue.
- If the node is null, set nullSeen = true.
Return true after processing all nodes.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        q = deque([root])
        nullSeen = False
        while q:
            node = q.popleft()
            if node:
                if nullSeen:
                    return False
                q.append(node.left)
                q.append(node.right)
            else:
                nullSeen = True
        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Depth First Search (Two Pass)

Intuition

A complete binary tree with n nodes has a specific property: if we number nodes starting from 0 (root) where a node at index i has children at 2i+1 and 2i+2, then every node's index must be less than n. First count all nodes, then verify that no node has an index >= n.

Algorithm

First pass: Count the total number of nodes in the tree using DFS.
Second pass: Perform DFS with indices, starting from (root, 0).
- If a node is null, return true.
- If a node's index >= total count, return false (gap exists).
- Recursively check left child (index 2i+1) and right child (index 2i+2).
Return true if all nodes pass the index check.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        def dfs(node, index, n):
            if not node:
                return True
            if index >= n:
                return False

            left = dfs(node.left, 2 * index + 1, n)
            right = dfs(node.right, 2 * index + 2, n)
            return left and right

        def countNodes(node):
            if not node:
                return 0
            return 1 + countNodes(node.left) + countNodes(node.right)

        n = countNodes(root)
        return dfs(root, 0, n)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

4. Depth First Search (Optimal)

Intuition

We can verify completeness in a single DFS pass by tracking the tree's height and whether we have seen a "short" path (one that ends before the maximum depth). In a complete tree, all paths to null nodes at the deepest level must appear before any paths ending one level higher, when traversing left to right.

Algorithm

Track the tree height (initialized to 0) and a flag nullSeen (for detecting gaps).
Perform DFS, tracking the current height:
- When reaching a null node, set treeHgt if not set.
- If the null is at height (treeHgt - 1), mark nullSeen = true.
- If the null is at treeHgt after nullSeen is true, return false (gap detected).
Recursively check left then right children.
Return true if no gaps are detected.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        treeHgt = 0
        nullSeen = False

        def dfs(node, hgt):
            nonlocal treeHgt, nullSeen
            if not node:
                if treeHgt == 0:
                    treeHgt = hgt
                elif hgt == treeHgt - 1:
                    nullSeen = True
                elif hgt != treeHgt:
                    return False
                return not (hgt == treeHgt and nullSeen)

            return dfs(node.left, hgt + 1) and dfs(node.right, hgt + 1)

        return dfs(root, 0)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

Common Pitfalls

Not Adding Null Children to Queue

When using BFS, both left and right children must be added to the queue even if they are null. Skipping null children prevents detection of gaps in the tree, since the null marker is needed to identify when a non-null node appears after a gap.

# Wrong: only adds non-null children
if node.left:
    q.append(node.left)
# Correct: always add both children
q.append(node.left)
q.append(node.right)

Checking Only Immediate Children for Completeness

A tree can have a missing left child but present right child, which violates completeness. Simply checking if both children exist misses cases where a null appears in the middle of a level.

# Wrong: only checks current node's children
if node.left is None and node.right is not None:
    return False
# Correct: track if any null seen, then check for non-null after
if node and nullSeen:
    return False

Wrong Index Formula in DFS Approach

When using array-based indexing (root at 0, children at 2i+1 and 2i+2), using incorrect formulas causes false positives. A common mistake is using 2i and 2i+1, which corresponds to 1-indexed arrays instead of 0-indexed.

# Wrong: 1-indexed formula with 0-indexed array
left_child = 2 * index
right_child = 2 * index + 1
# Correct: 0-indexed formula
left_child = 2 * index + 1
right_child = 2 * index + 2