Count Complete Tree Nodes — LC 222 Deep Dive

Problem Statement#

LeetCode 222 — Count Complete Tree Nodes | Difficulty: Medium

Given the root of a complete binary tree, return the number of nodes in the tree. A complete binary tree has every level fully filled except possibly the last level, which is filled from left to right.

Constraints:

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

Example 1:

Input: root = [1,2,3,4,5,6]
 
        1
       / \
      2   3
     / \ /
    4  5 6
 
Output: 6
Explanation: 6 nodes total; last level filled left to right.

Example 2:

Input: root = []
Output: 0
Explanation: Empty tree has 0 nodes.

Example 3:

Input: root = [1]
Output: 1
Explanation: Single root node.

Why This Problem Matters#

The naive approach — traversing every node — runs in O(n). Every interviewer who asks this problem is testing whether you recognize the O(log^2 n) shortcut that is unique to complete binary trees. This question shows up at FAANG companies because it sits at the intersection of tree structure, binary search thinking, and bit manipulation. Recognising that a specialized tree shape unlocks a faster algorithm is exactly the kind of pattern-recognition interviewers want to see. It also touches 1 << h for powers of two, which is a common bit-manipulation idiom.

The Core Insight#

In a perfect binary tree of height h (counting the root), the node count is exactly 2^h - 1. A complete binary tree either is perfect, or it contains at least one perfect subtree as a sub-problem.

The trick: at any node, compute the height by walking all the way left (call it lh), then independently compute it by walking all the way right (rh).

• If lh == rh: the subtree is a perfect binary tree. Return (1 << lh) - 1 with no further traversal.
• If lh != rh: the subtree is not perfect, but one of the two children must be perfect (one level shorter). Recurse on both children.

Each recursive call either short-circuits immediately (perfect subtree found) or recurses deeper. Since at every level exactly one child is always a perfect subtree, the recursion has at most O(log n) active branches, each requiring an O(log n) height check. Total: O(log^2 n).

Visual Dry Run#

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

        1          <- root
       / \
      2   3
     / \ /
    4  5 6

Step 1 — at root (node 1):

• Left spine: 1 → 2 → 4, so lh = 3
• Right spine: 1 → 3 → 6, but node 3 has no right child, so rh = 2
• lh (3) != rh (2) → not perfect → recurse on both children

Step 2 — at node 2 (left child of root):

• Left spine: 2 → 4, lh = 2
• Right spine: 2 → 5, rh = 2
• lh == rh == 2 → perfect subtree → return (1 << 2) - 1 = 3

Step 3 — at node 3 (right child of root):

• Left spine: 3 → 6, lh = 2
• Right spine: 3 → null, rh = 1
• lh != rh → recurse on both children of node 3

Step 4 — at node 6 (left child of 3):

• lh = rh = 1 → perfect → return (1 << 1) - 1 = 1

Step 5 — at node 3's right child (null):

• Base case → return 0

Bubbling up:

• Node 3: 1 (self) + 1 (node 6) + 0 (null) = 2
• Root: 1 (self) + 3 (node 2 subtree) + 2 (node 3 subtree) = 6 ✓

Common Mistakes#

1. Using O(n) traversal — Simply DFS-counting every node is correct but defeats the entire purpose of this problem in an interview context. The question is specifically designed to test the log^2 n shortcut.

2. Mixing spine directions — Left height must be measured by walking left at every step; right height by walking right. Mixing them produces a meaningless number.

3. Off-by-one in the power-of-two formula — When height h is the number of nodes on the path from root to deepest leaf (inclusive), a perfect tree has 2^h - 1 nodes. If you count edges instead of nodes, the formula becomes 2^(h+1) - 1. Be consistent about what h means.

4. Forgetting the null base case — Always return 0 when root is null before computing any heights. Dereferencing a null pointer to get its children will crash.

5. Assuming the shortcut only applies at the root — The perfect-tree check applies at every node encountered during recursion. Each recursive call independently short-circuits if its sub-problem is perfect.

6. Integer overflow with bit shifts — In JavaScript, 1 << 31 becomes negative due to signed 32-bit integers. For the given constraints (n up to 5 × 10^4, max height ~16), this is safe, but reason about it on the spot if asked.

Solutions#

# Python — O(log^2 n) complete-tree shortcut
def countNodes(root):
    # Base case: empty tree contributes 0 nodes
    if not root:
        return 0
 
    # Walk left spine to measure left height
    lh = 0
    node = root
    while node:
        lh += 1
        node = node.left
 
    # Walk right spine to measure right height
    rh = 0
    node = root
    while node:
        rh += 1
        node = node.right
 
    # Equal heights → this subtree is a perfect binary tree
    # A perfect tree of height h has (2^h - 1) nodes
    if lh == rh:
        return (1 << lh) - 1
 
    # Unequal heights → recurse; one child will always be perfect
    return 1 + countNodes(root.left) + countNodes(root.right)

// JavaScript — O(log^2 n) complete-tree shortcut
function countNodes(root) {
    // Null node contributes 0 nodes
    if (!root) return 0;
 
    // Measure left spine height
    let lh = 0, node = root;
    while (node) { lh++; node = node.left; }
 
    // Measure right spine height
    let rh = 0;
    node = root;
    while (node) { rh++; node = node.right; }
 
    // Equal heights: perfect subtree — return node count via bit shift
    // (1 << lh) is 2^lh; subtract 1 for the formula 2^h - 1
    if (lh === rh) return (1 << lh) - 1;
 
    // Unequal: one child is guaranteed perfect — recurse on both
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Complexity Analysis#

The shortcut: at most O(log n) recursive levels, each doing an O(log n) height walk → O(log n × log n) = O(log^2 n) total.

Follow-up Questions#

• What if the tree is not complete? You lose the height shortcut and must fall back to O(n) traversal, since there is no guarantee about subtree perfection.
• Can you do it iteratively? Yes — simulate the recursion with an explicit stack, though the recursive version is cleaner.
• Alternative O(log^2 n) approach? Binary search on the last-level positions: use left/right height comparison to determine which half of the last level contains the rightmost filled node, then narrow down. Same asymptotic complexity, slightly more complex implementation.

This Pattern Solves#

• Counting nodes in any tree where subtree shape can be determined in O(log n)
• Any divide-and-conquer problem where detecting a "trivial" sub-problem in sub-linear time avoids a full traversal
• Binary search applied to tree structure (not just sorted arrays)
• Problems that combine height measurement with recursive decomposition

Key Takeaways#

• Compare left spine height and right spine height at each node: if equal, the subtree is perfect and has exactly 2^h - 1 nodes
• A complete binary tree always has at least one perfect child subtree at every level — this is what enables the O(log^2 n) shortcut
• Never use O(n) traversal for this problem in an interview — the O(log^2 n) approach is the expected answer
• The bit shift (1 << lh) - 1 computes 2^h - 1 — use it to count perfect subtree nodes in O(1)
• Height is measured by walking the spine (all-left or all-right), not by general recursion
• Time O(log^2 n), space O(log n) for the recursion stack — both better than O(n)/O(n) naive traversal
• This "detect perfect subtree structure to skip counting" pattern generalizes to any divide-and-conquer problem with predictable subproblem structure