Check Completeness of a Binary Tree

Problem

Determine if a binary tree is complete (all levels fully filled except possibly last, last level filled left to right).

Key insight: BFS. The moment we see a null child, all subsequent nodes must also be null.

Solutions

// C
bool isCompleteTree(TreeNode* root) {
    if (!root) return true;
    TreeNode* queue[10001];
    int front = 0, back = 0;
    queue[back++] = root;
    bool seenNull = false;
    while (front < back) {
        TreeNode* node = queue[front++];
        if (!node) { seenNull = true; continue; }
        if (seenNull) return false;
        queue[back++] = node->left;
        queue[back++] = node->right;
    }
    return true;
}

// C++
bool isCompleteTree(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    bool seenNull = false;
    while (!q.empty()) {
        auto node = q.front(); q.pop();
        if (!node) { seenNull = true; continue; }
        if (seenNull) return false;
        q.push(node->left);
        q.push(node->right);
    }
    return true;
}

// Java
public boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    boolean seenNull = false;
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        if (node == null) { seenNull = true; continue; }
        if (seenNull) return false;
        q.add(node.left);
        q.add(node.right);
    }
    return true;
}

// JavaScript
function isCompleteTree(root) {
    const q = [root];
    let seenNull = false;
    while (q.length) {
        const node = q.shift();
        if (!node) { seenNull = true; continue; }
        if (seenNull) return false;
        q.push(node.left, node.right);
    }
    return true;
}

# Python
from collections import deque

def isCompleteTree(root):
    q = deque([root])
    seen_null = False
    while q:
        node = q.popleft()
        if node is None:
            seen_null = True
            continue
        if seen_null:
            return False
        q.append(node.left)
        q.append(node.right)
    return True

Complexity

Time: O(n)
Space: O(n)

Key Insight

Enqueue null children too. First null breaks the completeness assumption — any subsequent non-null is a violation.