Check Completeness of a Binary Tree

Med

#0912Time: O(N), where N is the number of nodes. We visit each node exactly once.Space: O(H), where H is the height of the tree, due to the recursion stack. For a complete tree, H is O(log N). For a skewed tree, H is O(N).1 company

Algorithms

Breadth-First Search

Data structures

Tree Binary Tree

Companies

Lyft

Prompt

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 2^h 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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a Depth-First Search (DFS) traversal. We can attempt to determine if a tree is complete by treating it as if it were stored in an array, where each node has a specific index. For a node at index i, its left child is at 2*i and its right child is at 2*i+1. A tree would be complete if the total number of nodes equals the maximum index found. However, this approach has a critical flaw for deep trees.

Algorithm

Create a helper DFS function, say dfs(node, index).
In the main function, initialize node_count = 0 and max_index = 0.
Call dfs(root, 1).
After the call returns, compare node_count and max_index. Return true if they are equal, false otherwise.
The dfs(node, index) function:
- If node is null, return.
- Increment node_count.
- Update max_index = max(max_index, index).
- Recursively call dfs(node.left, 2 * index).
- Recursively call dfs(node.right, 2 * index + 1).

Walkthrough

The idea is to assign an "ID" or "index" to each node. The root is assigned index 1. For any node at index i, its left child gets index 2*i and its right child gets 2*i+1.

We perform a DFS traversal of the tree, counting the total number of nodes and finding the maximum index assigned to any node. After the traversal, we compare the count and the max index. If they are equal, the tree is complete.

This logic works for 'bushy' trees, but fails for deep, skewed trees due to integer overflow, as the index can grow exponentially with depth.

1// NOTE: This solution is flawed and will fail for deep, skewed trees due to integer overflow.2class Solution {3    private int count = 0;4    private long maxIndex = 0; // Using long to delay overflow, but it still happens for N > 625 6    public boolean isCompleteTree(TreeNode root) {7        if (root == null) {8            return true;9        }10        dfs(root, 1L);11        return count == maxIndex;12    }13 14    private void dfs(TreeNode node, long index) {15        if (node == null) {16            return;17        }18        count++;19        maxIndex = Math.max(maxIndex, index);20        // Stop recursion to prevent overflow, but this is just a patch.21        // A correct solution shouldn't rely on indices that can grow this large.22        if (index >= Long.MAX_VALUE / 2) return;23        dfs(node.left, 2 * index);24        dfs(node.right, 2 * index + 1);25    }26}

Complexity

Time

O(N), where N is the number of nodes. We visit each node exactly once.

Space

O(H), where H is the height of the tree, due to the recursion stack. For a complete tree, H is O(log N). For a skewed tree, H is O(N).

Trade-offs

Pros

For trees that are 'bushy' or close to complete, it is more space-efficient (O(log N)) than BFS (O(N)).

Cons

The logic is less intuitive than the BFS approach.
Critically, the node indices can grow exponentially with the depth of the tree (2^depth). For a skewed tree with N nodes, the depth can be N. With N=100, the index 2^99 would overflow even a 64-bit integer (long), making this approach fail for deep, sparse trees that are permitted by the problem constraints.
Relies on recursion, which can lead to stack overflow for extremely deep trees (also an issue with N=100).

This approach uses Breadth-First Search (BFS) to traverse the tree level by level. It is a robust and intuitive method for this problem. The core idea is that in a complete binary tree, once a null node is encountered in the level-order traversal, all subsequent nodes must also be null.

Algorithm

If the root is null, return true (an empty tree is complete).
Initialize a queue (java.util.Queue) and add the root to it.
Initialize a boolean flag endFound = false.
Loop while the queue is not empty:
- Dequeue the current node.
- If the current node is null, set endFound = true.
- If the current node is not null:
  - If endFound is true, it means we found a node after a null gap. Return false.
  - Enqueue the left child (node.left).
  - Enqueue the right child (node.right).
If the loop finishes, return true.

Walkthrough

We perform a level-order traversal starting from the root using a queue.

We iterate through the tree level by level. When we encounter the first null node, it signifies the potential end of the tree's nodes.

We use a boolean flag, endFound, initialized to false. When we dequeue a null node, we set this flag to true.

If we ever dequeue a non-null node after endFound has been set to true, it means there's a gap in the tree, violating the "as far left as possible" rule. In this case, the tree is not complete, and we return false.

If a node is not null, we enqueue its left and right children, even if they are null. This is crucial to detect gaps.

If the traversal completes without violating the condition, the tree is complete, and we return true.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean isCompleteTree(TreeNode root) {18        if (root == null) {19            return true;20        }21 22        Queue<TreeNode> queue = new LinkedList<>();23        queue.offer(root);24        boolean endFound = false;25 26        while (!queue.isEmpty()) {27            TreeNode currentNode = queue.poll();28 29            if (currentNode == null) {30                endFound = true;31            } else {32                if (endFound) {33                    return false; // Found a non-null node after a null node34                }35                queue.offer(currentNode.left);36                queue.offer(currentNode.right);37            }38        }39        return true;40    }41}

Complexity

Time

O(N), where N is the number of nodes in the tree. Each node is enqueued and dequeued exactly once.

Space

O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), the last level can contain up to `ceil(N/2)` nodes, so the space complexity is O(N).

Trade-offs

Pros

Intuitive and directly follows the definition of a complete binary tree.
Robust and works correctly for all trees within the given constraints.
Relatively easy to implement.

Cons

Can be less space-efficient than a DFS approach for 'bushy' trees where the width W is proportional to N.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isCompleteTree ( TreeNode root ) { Deque < TreeNode > q = new LinkedList <>(); q . offer ( root ); while ( q . peek () != null ) { TreeNode node = q . poll (); q . offer ( node . left ); q . offer ( node . right ); } while (! q . isEmpty () && q . peek () == null ) { q . poll (); } return q . isEmpty (); } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCompleteTree ( TreeNode * root ) { queue < TreeNode *> q { { root } }; while ( q . front ()) { root = q . front (); q . pop (); q . push ( root -> left ); q . push ( root -> right ); } while ( ! q . empty () && ! q . front ()) q . pop (); return q . empty (); } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isCompleteTree ( self , root : TreeNode ) -> bool : q = deque ([ root ]) while q : node = q . popleft () if node is None : break q . append ( node . left ) q . append ( node . right ) return all ( node is None for node in q )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem