Watch 10 video solutions for Check Completeness of a Binary Tree, a medium level problem involving Tree, Breadth-First Search, Binary Tree. This walkthrough by Nick White has 21,237 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, determine if it is a complete binary tree.
In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: root = [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible.
Constraints:
[1, 100].1 <= Node.val <= 1000Problem Overview: You are given the root of a binary tree and must determine whether the tree is complete. A complete binary tree fills every level from left to right, except possibly the last level where nodes must appear as far left as possible.
Approach 1: Level Order Traversal with Queue (O(n) time, O(n) space)
This approach uses Breadth-First Search to traverse the tree level by level. Push nodes into a queue and process them in order. Once a null node appears during traversal, every node that follows must also be null. If a non-null node appears after a null, the structure violates the left-packed property of a complete binary tree. The key insight is that BFS naturally exposes gaps in the tree structure when scanning level order.
Each node is enqueued once and dequeued once, giving O(n) time complexity and O(n) auxiliary space for the queue in the worst case. This approach is intuitive because completeness is defined based on level order structure.
Approach 2: DFS with Node Counting (O(n) time, O(n) space)
This method relies on indexing nodes the same way an array represents a binary heap. First count the total number of nodes using a DFS traversal of the tree. Then perform another DFS where each node is assigned an index: root = 0, left child = 2*i + 1, right child = 2*i + 2. If any node receives an index greater than or equal to the total node count, the tree cannot be complete.
The insight comes from how complete binary trees map perfectly to array indices with no gaps. A missing internal node causes an index jump beyond the expected range. The traversal visits each node once, so the time complexity is O(n). Recursive DFS requires up to O(h) stack space, which becomes O(n) in the worst case for skewed trees. This approach leverages structural properties of a binary tree and is common in theoretical discussions.
Recommended for interviews: The level order traversal with a queue is the approach most interviewers expect. It directly models the definition of completeness and is easy to reason about during whiteboard discussion. The DFS indexing method demonstrates deeper understanding of tree-to-array mappings and is a strong alternative once you recognize the heap-style indexing property.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal with Queue | O(n) | O(n) | Best general solution. Directly verifies completeness using BFS order. |
| DFS with Node Counting and Indexing | O(n) | O(n) | Useful when reasoning about heap-style indexing or validating structural properties. |