Check Completeness of a Binary Tree
Medium · Trees · Tree · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return true if it is a complete binary tree, and false otherwise.
A binary tree is complete when every level except possibly the last is completely filled, and the nodes of the last level are as far left as possible. The last level may hold anywhere from one node up to a full level.
Trees are shown as level-order lists, with null for a missing child.
Examples
Input: root = [1,2,3,4,5,6] Output: true
The first two levels are full and the last level [4,5,6] is packed to the left.
Input: root = [1,2,3,4,null,6] Output: false
Node 2 has no right child, yet node 6 comes after that gap on the same level.
Constraints
- 1 <= number of nodes <= 100
- 1 <= Node.val <= 1000
Approaches
- Look up every heap slot — time O(n log n), space O(h)
Follow-up
How would you count the nodes of a tree you already know is complete, faster than visiting all of them? Compare the leftmost and rightmost depths of each subtree: when they match, the subtree is perfect and has 2^h − 1 nodes, so only one path needs exploring, for O(log² n) in total.
Related problems
Start free on Cariara · Coding problems · System design studio
