DSA problem
Check Completeness of a Binary Tree
Given the root of a binary tree, determine if it is a complete binary tree. A complete binary tree is one in which every level except possibly the last is completely filled, and all nodes on the last level are as far left as possible.
The key insight that makes a BFS solution clean is this: if we walk the tree in level-order and push BOTH children of every node into the queue — even when a child is null — then a complete tree corresponds to a contiguous prefix of non-null entries followed by a (possibly empty) trailing run of nulls. Any non-null entry seen AFTER a null means the tree is not complete.
So our algorithm is to BFS the tree while pushing every left and right reference (including null). We maintain a single boolean seenNull, initially false. Each iteration, we pop the front and check: if the popped value is null we set seenNull = true and continue; if the popped value is non-null but seenNull is already true, we immediately return false because we have just found a node that violates the "fill left first" rule. If we drain the queue without returning false, the tree is complete.
This is a one-pass O(n) algorithm. The queue contains at most O(w) non-null nodes plus O(w) nulls on the deepest fringe, giving O(w) extra space.
Examples
root = [1,2,3,4,5,6]trueroot = [1,2,3,4,5,null,7]falseroot = [1]trueConstraints
- The number of nodes in the tree is in the range [1, 100].
- 1 <= Node.val <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.