Count Nodes in a Complete Binary Tree — LC 222 O(log^2 n) Proof

Problem Statement#

LeetCode 222 — Count Complete Tree Nodes | Difficulty: Medium

Given the root of a complete binary tree, return the number of nodes. In a complete binary tree, every level is fully filled except possibly the last, which is filled left to right. Design an algorithm faster than O(n).

Constraints:

• The number of nodes is in the range [0, 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• The tree is a complete binary tree

Input:  root = [1,2,3,4,5,6]
Output: 6

Input:  root = []
Output: 0

Why This Problem Matters#

This problem is a FAANG interview trap: the naive O(n) DFS answer is technically correct but misses the expected O(log^2 n) insight. Amazon and Google ask it specifically to see whether you recognize that a complete binary tree's structure enables a smarter algorithm. Saying "just traverse all nodes" in an interview for this problem signals you missed the structural constraint.

The key insight — comparing left and right spine heights to detect perfect subtrees — is the same technique used in binary indexed trees, segment trees for ranges, and any algorithm that exploits "nearly full" binary structure.

The Core Insight#

At any node in a complete binary tree, compare:

• Left height lh: walk left at every step until null
• Right height rh: walk right at every step until null

If lh == rh: the subtree rooted here is a perfect binary tree with exactly 2^lh - 1 nodes. Return immediately without recursing.

If lh != rh: one of the two children must be a perfect subtree (the complete tree property guarantees this). Recurse on both children.

Why does this work? In a complete binary tree:

• If left height equals right height, all levels are fully filled — it is a perfect tree
• If left height is greater than right height by exactly 1, the last level is partially filled — the right child's subtree is a shorter perfect tree, and the left child might not be

Each recursive call encounters O(log n) levels, and each level does an O(log n) height walk. Total: O(log^2 n).

Visual Dry Run#

Tree: [1, 2, 3, 4, 5, 6]

Total: 1 (root) + 3 (node 2 subtree) + 1 (node 3) + 1 (node 6) + 0 = 6.

Solution (Optimal)#

class Solution:
    def countNodes(self, root) -> int:
        if not root:
            return 0
 
        # Measure left spine height
        lh, node = 0, root
        while node:
            lh += 1
            node = node.left
 
        # Measure right spine height
        rh, node = 0, root
        while node:
            rh += 1
            node = node.right
 
        # Equal heights: perfect subtree — formula 2^h - 1
        if lh == rh:
            return (1 << lh) - 1
 
        # Recurse: at least one child is a perfect subtree
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

var countNodes = function(root) {
    if (!root) return 0;
 
    let lh = 0, node = root;
    while (node) { lh++; node = node.left; }
 
    let rh = 0;
    node = root;
    while (node) { rh++; node = node.right; }
 
    if (lh === rh) return (1 << lh) - 1;
 
    return 1 + countNodes(root.left) + countNodes(root.right);
};

Time: O(log^2 n) — O(log n) recursive levels, each doing O(log n) height work Space: O(log n) — recursion stack depth

Common Mistakes#

• Naively traversing all nodes (O(n)) — correct but not what the interviewer wants
• Walking both spines left (or both right) instead of left-spine left and right-spine right
• Off-by-one in the perfect tree formula — height h (counting nodes) gives 2^h - 1 nodes
• Forgetting the null base case before computing heights

Interview Tips#

• State immediately that you will exploit the complete binary tree property for O(log^2 n)
• Explain why equal spine heights means perfect: all levels fully filled
• The (1 << lh) - 1 bit shift is clean — explain that it computes 2^lh - 1
• Contrast with the naive O(n) to show you understand why this is better

Follow-up Questions#

• What if the tree is not guaranteed to be complete? Fall back to O(n) DFS — there is no structural shortcut for arbitrary binary trees.
• Is there an O(log n) approach? Yes, using binary search on the last level — binary search over possible node counts in O(log n) queries, each taking O(log n) time, giving O(log^2 n). The recursive approach here achieves the same asymptotic bound.
• Why does at least one child always have a perfect subtree? The complete tree property means the last level is filled left to right — the right subtree is always a perfect subtree (shorter by one level than the left in the worst case).

Key Takeaways#

• Compare left spine height (walk all-left) and right spine height (walk all-right) at each node
• Equal heights means the subtree is perfect: return 2^h - 1 without further recursion
• Unequal heights means at least one child is a perfect subtree — recurse and combine
• The bit shift (1 << lh) - 1 computes 2^lh - 1 efficiently
• Time O(log^2 n), space O(log n) — both better than O(n)/O(n) naive traversal
• Never use O(n) node counting in an interview for this problem — the structural shortcut is the expected answer
• This pattern generalizes: whenever a tree structure guarantees perfect subtrees, you can use height comparison to skip counting them