Check Completeness of a Binary Tree

medium tree bfs

Problem

A complete binary tree has every level fully filled except possibly the last, and the last level fills left to right. Return whether the given binary tree is complete.

Inputtree = [1,2,3,4,5,null,7]

Outputfalse

BFS enqueues children (including nulls); the moment a null pops, no real node may follow.

level-order (use 'null')

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
        else:
            if seen_null: return False
            q.append(node.left)
            q.append(node.right)
    return True

function isCompleteTree(root) {
  const q = [root]; let head = 0, seenNull = false;
  while (head < q.length) {
    const node = q[head++];
    if (node === null) seenNull = true;
    else {
      if (seenNull) return false;
      q.push(node.left); q.push(node.right);
    }
  }
  return true;
}

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean seenNull = false;
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n == null) seenNull = true;
            else {
                if (seenNull) return false;
                q.offer(n.left); q.offer(n.right);
            }
        }
        return true;
    }
}

bool isCompleteTree(TreeNode* root) {
    queue<TreeNode*> q; q.push(root);
    bool seenNull = false;
    while (!q.empty()) {
        TreeNode* n = q.front(); q.pop();
        if (!n) seenNull = true;
        else {
            if (seenNull) return false;
            q.push(n->left); q.push(n->right);
        }
    }
    return true;
}

Explanation

A complete tree fills every level fully and packs the last level to the left. The clever observation is that if you do a level-order traversal and enqueue children including the nulls, then in a complete tree all the real nodes appear before any null gap.

So we run a BFS with a flag seenNull starting false. Each time we pop a node: if it is null, we set seenNull = true; if it is a real node, we first check the flag. Spotting a real node after a null means there was a hole, so we return false.

For every real node we enqueue both node.left and node.right even when they are null. Those nulls act as placeholders that reveal gaps later in the queue. If the queue drains without ever seeing a real-node-after-null, the tree is complete.

Example: [1, 2, 3, 4, 5, null, 7]. We pop 1, 2, 3, 4, 5, then a null (the missing left child of 3) which sets the flag, then the real node 7 appears — a node after a null — so the answer is false.

Each node and its placeholder children are processed once, giving O(n) time.

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