Check Completeness of a Binary Tree
Given the root of a binary tree, determine if it is a complete binary tree. Use Breadth-First Search (BFS) for an efficient check.
Why Interviewers Ask This
Adobe evaluates this question to assess a candidate's ability to translate theoretical tree properties into efficient, production-ready code. They specifically look for mastery of Breadth-First Search (BFS) and the capacity to handle edge cases like null pointers or single-node trees without recursion overhead.
How to Answer This Question
1. Clarify the definition: Explicitly state that a complete binary tree must be filled level-by-level from left to right with no gaps until the last level.
2. Propose BFS Strategy: Suggest using a queue to traverse level-order, as this naturally exposes the structural order required.
3. Define the Stopping Condition: Explain the logic that once a null node is encountered, all subsequent nodes in the queue must also be null; otherwise, the tree is incomplete.
4. Handle Edge Cases: Mention checking for an empty root immediately before starting the traversal.
5. Complexity Analysis: Conclude by discussing time complexity O(N) and space complexity O(W), where W is the maximum width of the tree.
Key Points to Cover
- Explicitly defining the 'no gaps' rule for the last level
- Using a queue to enforce level-order traversal
- Implementing the 'null flag' logic to detect gaps efficiently
- Handling the empty tree edge case gracefully
- Analyzing time and space complexity clearly
Sample Answer
To determine if a binary tree is complete, I would use a Breadth-First Search approach because it processes nodes level by level, which aligns perfectly with the definition of completeness. First, I'd initialize a queue…
Common Mistakes to Avoid
- Attempting recursive solutions which complicate tracking the 'last level' state
- Failing to check if subsequent nodes are non-null after encountering the first null
- Ignoring the edge case where the root itself is null
- Confusing complete binary trees with full binary trees in the explanation
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.