Given the root of a complete binary tree, return the number of nodes in it.
In a complete binary tree every level is fully filled except possibly the last, and the last level's nodes are as far left as possible. A perfect tree of height h has exactly 2^h - 1 nodes.
Design an algorithm that runs in better than O(n) time. The tree is given in level-order (breadth-first), using null for missing children.
Input: root = [1, 2, 3, 4, 5, 6] Output: 6 The complete tree has 6 nodes.
Input: root = [] Output: 0 An empty tree has no nodes.
Input: root = [1] Output: 1 A single node.
- The number of nodes is in the range [0, 5 * 10^4] - 0 <= Node.val <= 5 * 10^4 - The tree is guaranteed to be complete
Counting every node is O(n) and ignores the gift of completeness. The trick: for any subtree, walk its leftmost spine and its rightmost spine. If the two heights match, the subtree is perfect and holds 2^h − 1 nodes — counted in O(h) with no recursion into it. Otherwise recurse into both children. Only the subtrees straddling the last level's boundary recurse, giving O(log²n).
“Is the tree guaranteed complete?”
Yes — that's what enables the sub-O(n) approach.
“What's the target complexity?”
Better than O(n); the spine trick gives O(log^2 n).
For any subtree I measure the left-spine and right-spine heights.
If they're equal the subtree is perfect with 2^h − 1 nodes; otherwise I recurse into both children, and completeness guarantees only O(log n) subtrees ever recurse.
Worked example — a complete tree with 6 nodes [1, 2, 3, 4, 5, 6]
1
/ \
2 3
/ \ /
4 5 6
root: lh (1-2-4) = 3, rh (1-3) = 2 -> not perfect, recurse
left subtree [2,4,5]: lh=rh=2 -> perfect, 2^2-1 = 3
right subtree [3,6]: lh=2, rh=1 -> recurse -> 2
total: 1 + 3 + 2 = 6
When the leftmost and rightmost paths are equally long, every level is full, so the count is 2^h − 1.
Completeness means at most one child per level is imperfect, so recursion depth is O(log n).
O(log n) recursive calls, each doing an O(log n) spine measurement.
| Count every node | Spine-height shortcut | |
|---|---|---|
| Idea | 1 + count(left) + count(right) | Perfect subtree -> 2^h - 1, else recurse |
| Time | O(n) | O(log^2 n) |
| Space | O(height) | O(height) |
The shortcut exploits completeness to skip whole perfect subtrees. Full code is in the Approaches selector below.
Key takeaway
Measure left-spine and right-spine heights. Equal ⇒ perfect subtree of 2^h − 1 nodes (O(h)); otherwise recurse into both children. Completeness bounds this to O(log²n).
count(node):
if node is null: return 0
lh = left-spine height; rh = right-spine height
if lh == rh: return 2^lh - 1
return 1 + count(left) + count(right)