Check Completeness of a Binary Tree

Check Completeness of a Binary Tree

What is this problem about?

The "Check Completeness of a Binary Tree interview question" asks you to verify if a given binary tree is "complete." A complete binary tree is one where every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. This structural property is essential for representing trees in arrays (like in a Binary Heap).

Why is this asked in interviews?

Companies like Lyft and Meta ask the "Check Completeness of a Binary Tree coding problem" to test a candidate's knowledge of tree traversals, particularly Breadth-First Search (BFS). It evaluates your ability to recognize a specific pattern in the order nodes are visited. It also checks if you understand the conceptual difference between "full", "perfect", and "complete" trees.

Algorithmic pattern used

This problem is best solved using the Level Order Traversal (BFS) pattern.

1. Queue: Use a queue to perform a standard BFS.
2. Include Nulls: Unlike a typical BFS, you should add null children to the queue.
3. The "No-Null-Gap" Rule: In a complete tree, once you encounter a null node in a level-order traversal, you should never see another non-null node.
4. Validation: If you pop a null from the queue and subsequently pop a valid (non-null) node, the tree is not complete.

Example explanation

Tree: [1, 2, 3, 4, 5, null, 7]

1. Queue: [1]. Pop 1, push children 2, 3.
2. Queue: [2, 3]. Pop 2, push children 4, 5.
3. Queue: [3, 4, 5]. Pop 3, push children null, 7.
4. Queue: [4, 5, null, 7]. Pop 4, push null, null.
5. Queue: [5, null, 7, null, null]. Pop 5, push null, null.
6. Queue: [null, 7, null, null, null, null]. Pop null. Set a flag seen_null = true.
7. Pop 7. seen_null is true, but current node is not null! Result: False.

Common mistakes candidates make

• DFS Confusion: Trying to solve this with Depth-First Search is much harder because DFS doesn't naturally visit nodes in the left-to-right, level-by-level order required to check completeness.
• Ignoring the Last Level: Only checking if the upper levels are full but forgetting the "as far left as possible" rule for the bottom level.
• Queue Management: Forgetting to push the null children into the queue, which is the key to detecting "gaps."

Interview preparation tip

Master BFS for trees! Level-order traversal is the go-to "Tree interview pattern" for any problem that involves the shape or width of a tree. Always consider how null nodes affect the structure when properties like "completeness" are involved.