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.
This approach uses a level-order traversal technique with the help of a queue to check if the binary tree is complete. In a complete binary tree, once a null node is encountered while doing a level order traversal, all subsequent nodes must also be null to satisfy completeness.
The C implementation utilizes a custom queue for level-order traversal. We maintain a flag 'encounteredNull' to detect when a null node appears. If any non-null node is found after a null node has been dequeued, we return false immediately, indicating the tree is not complete.
Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once.
Space Complexity: O(n), where n is the number of nodes, used for the queue storage.
This approach utilizes depth-first search to gather information regarding the number of nodes and their indices. Using these, we check the compactness of the tree at each level to ensure all nodes fit the complete binary tree property.
In C, this solution counts the nodes first, then checks each node for a valid index based on complete tree properties using DFS.
Time Complexity: O(n).
Space Complexity: O(n), due to recursive stack usage.
| Approach | Complexity |
|---|---|
| Level Order Traversal with Queue | Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once. Space Complexity: O(n), where n is the number of nodes, used for the queue storage. |
| DFS with Node Counting | Time Complexity: O(n). Space Complexity: O(n), due to recursive stack usage. |
| Default Approach | — |
| 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. |
LeetCode Check Completeness of a Binary Tree Explained - Java • Nick White • 21,237 views views
Watch 9 more video solutions →Practice Check Completeness of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode