Check Completeness of a Binary Tree
Understanding the Problem
We need to check whether a binary tree satisfies the definition of a "complete" binary tree. This is a structural property: node values are irrelevant, only the shape matters.
A complete binary tree fills positions level by level, left to right, skipping none. Number every possible position starting from 1 at the root: the root's left child is position 2, its right child is position 3, and in general the children of position i are positions 2*i and 2*i + 1. In a complete binary tree, the occupied positions form a contiguous block from 1 to n, with no gaps.
The check therefore reduces to finding a gap in the level-order traversal. If a BFS encounters a null position, every position after it must also be null. A non-null node after a null means the tree is incomplete.
Key Constraints:
Number of nodes in [1, 100]-- The input is small, so a single O(n) traversal is more than enough. The lower bound of 1 also guarantees the root is never null, which removes the empty-tree edge case.1 <= Node.val <= 1000-- Values play no role in the check. Only the structure matters.
Approach 1: BFS with Null Flag
Intuition
Read the tree level by level, left to right. In a complete binary tree this sequence never has a gap: once an empty position appears, every position after it is also empty. A non-null node appearing after a null is the gap that breaks completeness.
A BFS can detect this directly, with one change from the usual pattern: enqueue the children of every non-null node, including the null children. Standard BFS skips nulls, but here the nulls mark the empty positions in the level-order sequence. When the first null is dequeued, set a flag. If any non-null node is dequeued after that, return false.
Algorithm
- Initialize a queue with the root node.
- Set a boolean flag
seenNullto false. - While the queue is not empty, dequeue the front node.
- If the node is null, set
seenNullto true. - If the node is not null and
seenNullis already true, return false (a gap exists). - If the node is not null, enqueue its left child and right child (even if they are null).
- If the loop finishes without returning false, return true.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Every node is enqueued and dequeued once, along with at most n + 1 null entries, and each queue operation is O(1).
- Space Complexity: O(n). In the worst case (a perfect binary tree), the last level holds roughly n/2 nodes, all in the queue at once, plus their null children.
The flag-based BFS inspects the level-order sequence directly. The same gap can also be detected arithmetically, by giving each node the array index it would occupy in a heap.
Approach 2: Node Indexing (Array Position Check)
Intuition
A binary tree maps onto an array the way a heap does: the root takes index 1, and a node at index i has its left child at 2*i and its right child at 2*i + 1. In a complete binary tree with n nodes, these indices are exactly 1 through n, with no gaps. In the tree [1, 2, 3, 4, 5, null, 7], node 7 is the right child of node 3, so it gets index 7 even though the tree has only 6 nodes. Index 6 (the missing left child of node 3) is unoccupied, so the tree is incomplete.
This gives a check that needs no null bookkeeping. Run a BFS that carries each node's index, enqueuing only non-null children, and count how many nodes have been dequeued. A complete tree's level order visits indices 1, 2, ..., n in order, so the k-th node dequeued must have index exactly k. Conversely, if every dequeued index matches its position, the index set is exactly {1, ..., n}, which means the occupied positions are contiguous and the tree is complete. The first mismatch proves a gap, and we return false immediately.
Comparing the index against the running position, rather than comparing the maximum index to the node count after the traversal, also keeps the numbers small. Index values double at every level, so computing them all the way down a deep skewed tree would push them past any fixed-width integer. With the early exit, only nodes that already passed the check (index at most n) get children enqueued, so every index computed stays at most 2n + 1.
Algorithm
- Run a BFS that stores
(node, index)pairs. The root gets index 1; a node with indexienqueues its left child with index2 * iand its right child with index2 * i + 1. Only non-null children are enqueued. - Keep a counter of how many nodes have been dequeued so far.
- When a node is dequeued, compare its index to the counter. If they differ, an earlier position is empty; return false.
- If every node's index matches its position, return true.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each node is dequeued once with O(1) work, and the loop exits at the first mismatched index.
- Space Complexity: O(n). The widest level holds about n/2 nodes; storing an index alongside each node does not change the bound. Index values stay at most 2n + 1, so they fit comfortably in a standard integer.