222 · Count Complete Tree Nodes

A trap problem. A plain O(n) traversal returns the right number and is the wrong answer: the word "complete" in the statement is not decoration, it is the algorithm. Whenever a tree problem names its shape, the shape is what you are being asked to exploit.

1 — The problem

Count the nodes in a complete binary tree: every level is full except possibly the last, and the last level is filled left to right. The follow-up asks for better than O(n), which rules out visiting every node.

Two facts do the work:

• A perfect tree of height h has exactly 2^h - 1 nodes — countable in O(1) with no traversal at all.
• In a complete tree, walking left from any node and walking right from that same node give equal heights if and only if that subtree is perfect. One walk down each edge, O(log n), decides it.

So at every node: measure the two spines. If they match, return the formula and stop. If they do not, recurse into both children — and here is the part worth stating out loud, because it is what bounds the running time: in a complete tree, at most one child per level can itself be imperfect. The recursion therefore follows a single root-to-leaf corridor, not a whole tree.

2 — Discarding half the tree per level

Twelve nodes. Watch node 2: its two spines both measure 3, so its entire seven-node subtree is settled by 2³ − 1 without a single one of those nodes being visited. The recursion then continues down the right, where the tree is ragged.

Count the nodes that were actually entered: 1, 2, 3, 6, 7, 12 and one null. Six of twelve, and the gap widens fast — on a complete tree with a million nodes the recursion enters roughly forty.

2.1 Why one spine each is enough

It is tempting to think you need to inspect the last level to know whether a subtree is perfect. You do not, and the reason is the completeness guarantee:

• The left spine is the longest possible path, because the last level fills from the left — if any node at depth d exists, the leftmost one does.
• The right spine is the shortest, by the mirror argument — the rightmost position at each depth is the last to be filled.
• If the longest and shortest agree, every path has that length, so the tree is perfect. If they differ, they differ by exactly 1, and the last level is partially filled.

Remove the completeness precondition and this collapses immediately: in an arbitrary tree the two spines can agree while the interior is full of holes. The algorithm is not "a clever way to count nodes" — it is a consequence of the shape, and it is only valid because the shape was promised.

3 — Complexity and edge cases

• Time O(log² n) — the recursion descends O(log n) levels, and each level pays O(log n) for the two spine walks. Space O(log n) for the stack.
• Empty tree: 0. The null guard covers it.
• Perfect tree: the very first spine comparison succeeds and the answer comes back in O(log n) with no recursion at all — the best case.
• Overflow: 1 << lh is fine for LeetCode's 5 × 10⁴ bound, but 1 << 31 is negative in Java. Use 1L << lh if heights can reach 31.
• Common bug: comparing subtree heights (left child's height vs right child's height) instead of the two spines of the same node. Those are different measurements, and the first one does not characterise perfection.
• The real failure mode is submitting the O(n) traversal, passing, and never learning the problem. It is listed here as an anti-pattern for exactly that reason.

4 — Reference implementation

public int countNodes(TreeNode nd) {
    if (nd == null) return 0;
    int lh = 0, rh = 0;
    for (TreeNode p = nd; p != null; p = p.left)  lh++;
    for (TreeNode p = nd; p != null; p = p.right) rh++;
    if (lh == rh) return (1 << lh) - 1;   // perfect — no traversal
    return 1 + countNodes(nd.left) + countNodes(nd.right);
}

The 1 + and the two recursive calls are the ordinary sub-variant A skeleton. The whole difference is the line above them, which lets most of those calls never happen.