Check Completeness of a Binary Tree — Problem & Solution
Check Completeness of a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Check Completeness of a Binary Tree is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, determine whether it is a complete binary tree.
In a complete binary tree every level is completely filled except possibly the last one, and all nodes of the last level are as far left as possible. (The last level h may hold anywhere from 1 to 2^h nodes.)
Example 1
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: The first two levels are full and the last one, 4 5 6, is packed to the left.
Example 2
Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: On the last level there is a gap (3 has no left child) before 7.
Example 3
Input: root = [1,2,3,null,4]
Output: false
Explanation: 2 has a right child but no left child, so the last level is not packed to the left.
Constraints
The number of nodes in the tree is in the range [1, 100]1 <= Node.val <= 1000
Hints for Check Completeness of a Binary Tree
Hint 1
Read the tree in level order, writing down a marker for every missing child as well as every node.
Hint 2
In a complete tree, all the real nodes come first and all the missing ones after — once you meet a gap, nothing real may follow.
Hint 3
So run a BFS that also enqueues null children; after the first null is dequeued, any non-null node means the tree is not complete.
How to solve Check Completeness of a Binary Tree
A complete tree, read level by level from left to right, is a contiguous run of nodes followed only by empty slots. A BFS that enqueues null children sees exactly that sequence, so the tree is complete if no node appears after the first null.
Approach
- Put the root in a queue and set
seenGap = false. - Dequeue an entry. If it is null, set
seenGap = trueand continue. - If it is a node and
seenGapis already true, return false. Otherwise enqueue both of its children, null or not. - If the queue empties without a violation, return true.
Why it works
The BFS produces the nodes in the order of their positions in a complete-tree numbering, with a null at every missing position whose parent exists. The tree is complete exactly when the occupied positions are 1..n with no hole, i.e. when no real node follows a null in that order.
Complexity
- Time —
O(n) - Space —
O(n) for the queue
Pitfalls
- Enqueue null children too — skipping them hides the gaps the check is looking for.
- A node with a right child but no left child is never complete.
- Checking only that every level but the last is full is not enough; the last level must also be packed to the left.
Reference solution
Python
from typing import Optional
def isCompleteTree(root: Optional[TreeNode]) -> bool:
queue = [root]
head = 0
seen_gap = False
while head < len(queue):
node = queue[head]
head += 1
if node is None:
seen_gap = True
continue
if seen_gap:
return False
queue.append(node.left)
queue.append(node.right)
return TrueJava
public static boolean isCompleteTree(TreeNode root) {
List<TreeNode> queue = new ArrayList<>();
queue.add(root);
boolean seenGap = false;
for (int h = 0; h < queue.size(); h++) {
TreeNode node = queue.get(h);
if (node == null) { seenGap = true; continue; }
if (seenGap) return false;
queue.add(node.left);
queue.add(node.right);
}
return true;
}C++
bool isCompleteTree(TreeNode* root) {
vector<TreeNode*> queue = {root};
bool seenGap = false;
for (size_t h = 0; h < queue.size(); h++) {
TreeNode* node = queue[h];
if (!node) { seenGap = true; continue; }
if (seenGap) return false;
queue.push_back(node->left);
queue.push_back(node->right);
}
return true;
}JavaScript
var isCompleteTree = function(root) {
var queue = [root], seenGap = false;
for (var h = 0; h < queue.length; h++) {
var node = queue[h];
if (node === null) { seenGap = true; continue; }
if (seenGap) return false;
queue.push(node.left);
queue.push(node.right);
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals