Count Complete Tree Nodes
Count Complete Tree Nodes: count the nodes of a complete binary tree in better than O(n) time, exploiting the shape rather than visiting every node.
- The number of nodes is in the range [0, 5 * 10⁴]
- 0 <= Node.val <= 5 * 10⁴
- The tree is guaranteed to be complete
Intuition
In a complete tree every level is full except possibly the last, which fills left to right. A perfect subtree of height h holds exactly 2^h - 1 nodes — countable by formula with no traversal. Measuring the leftmost and rightmost depths tells you whether a subtree is perfect; if it is, apply the formula, and if not, recurse into the two children, only one of which can be imperfect.
When a problem guarantees structure — complete, sorted, balanced — the intended solution almost always beats the generic one by exploiting it. The tell here is the explicit complexity demand alongside the completeness guarantee.
Approach
Before reading on: work out why equal leftmost and rightmost depths prove a complete subtree is perfect. Then argue why at most one child of any node can be imperfect, and what that implies for the recursion's cost.
Detecting a perfect subtree in O(log n)
Walk left children to the deepest level and count the steps, then do the same following right children. In a complete tree these two depths are equal exactly when the subtree is perfect: completeness means the last level fills from the left, so if the rightmost path reaches the same depth as the leftmost, no gap can exist anywhere between them. Each probe follows a single root-to-leaf path, so the test costs O(log n) rather than a full traversal.
Formula when perfect, recursion when not
If the depths match, return 2^h - 1 — a shift, (1 << h) - 1, with no recursion at all. If they differ, the subtree is not perfect, so return 1 + count(left) + count(right). The key structural fact is that at most one of those two children can itself be imperfect: the last level fills left to right, so the deficiency lies entirely in one child while the other is perfect and terminates immediately by formula. That is what prevents the recursion from degenerating into a full walk.
Why the total is O(log² n)
The recursion descends at most one imperfect branch per level, so it visits O(log n) nodes overall. At each of those, the two depth probes cost O(log n). Multiplying gives O(log² n) — for a tree of 5 × 10⁴ nodes that is a few hundred operations instead of fifty thousand. Space is O(log n) for the recursion stack. A plain 1 + count(left) + count(right) is correct and far simpler, but it is O(n) and ignores the completeness the problem supplies.
Solution & live demo
Common pitfalls
Counting every node
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
test for a perfect subtree first, then apply the formula
Correct but O(n), which ignores the completeness guarantee the problem provides and fails the stated requirement to do better than visiting every node.
Off-by-one in the node-count formula
return (1 << left_depth)
return (1 << left_depth) - 1
A perfect tree of height h has 2^h - 1 nodes, not 2^h. Levels contribute 1 + 2 + 4 + … + 2^(h-1), which sums to one less than the next power of two.
Comparing height instead of depth along the two edges
if height(root.left) == height(root.right):
if depth(root, left) == depth(root, right):
Comparing the children's heights does not establish perfection of the whole subtree — the left child may be perfect and the right child deficient while their heights still differ by one, which is the normal case for a complete tree.
Edge cases
The height probe returns 0 immediately and the count is 0.
The depths match at the root, so one formula call answers it with no recursion.
Both depths are 1, giving 2¹ - 1 = 1.
The depths differ at the root, and recursion resolves the left child by formula.
The left child is perfect and the right child is one level shallower and perfect.