Check Completeness of a Binary Tree - Solution & Explanation
Problem Statement
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:
- The number of nodes in the tree is in the range
[1, 100]. 1 <= Node.val <= 1000
Approach Overview
Problem 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 1: Level Order Traversal with Queue
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.
Complexity
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.
Approach 2: DFS with Node Counting
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.
Complexity
Time Complexity: O(n).
Space Complexity: O(n), due to recursive stack usage.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
LeetCode Check Completeness of a Binary Tree Explained - Java • Nick White • 21,301 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check Completeness of a Binary Tree easy or hard?
Check Completeness of a Binary Tree Python/Java solution
How to solve Check Completeness of a Binary Tree in O(n)?
What is the best approach for Check Completeness of a Binary Tree?
Is Check Completeness of a Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Check Completeness of a Binary Tree?
What is the time complexity of Check Completeness of a Binary Tree?
Ready to solve this problem?
Practice Check Completeness of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode