Count Complete Tree Nodes

Difficulty: Easy
Topics: Binary Search, Bit Manipulation, Tree, Binary Tree
Link: https://leetcode.com/problems/count-complete-tree-nodes/

Problem Description

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:


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

Example 2:


Input: root = []
Output: 0

Example 3:


Input: root = [1]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
Given the root node of a complete binary tree, compute the total number of nodes using an algorithm with sub-linear time complexity. A complete binary tree satisfies the property that all levels except possibly the last are completely filled, and all nodes in the last level are positioned as far left as possible. The solution must exploit these structural constraints to avoid visiting every node individually.

Beginner-Friendly Explanation
Imagine you have a perfectly organized family tree where each parent has exactly two children, and all levels are completely filled except possibly the bottom row. In that bottom row, people are seated starting from the leftmost position. Your task is to count everyone in this family tree without asking each person individually. You need a clever strategy that uses the tree’s organized structure to count faster than checking everyone one-by-one.

Mathematical Formulation
Let:

$h$ = height of the tree (root at height 0)
$L$ = set of nodes in last level
$N_{perfect}(h) = 2^{h+1} - 1$ = nodes in perfect binary tree of height $h$

For a complete binary tree:

Levels $0$ to $h-1$ contain $2^h - 1$ nodes
Last level contains between $1$ and $2^h$ nodes
Total nodes = $(2^h - 1) + |L|$ where $1 \leq |L| \leq 2^h$

Constraint Analysis

Number of nodes in range [0, 5 × 10⁴]:
This prevents O(n²) solutions but allows O(n) brute force. The challenge is achieving sub-linear O(log² n) performance. At maximum size, O(n) would process 50,000 nodes while O(log² n) processes ~225 operations.
Tree guaranteed to be complete:
This is the critical constraint enabling optimization. We can assume:
1. Left and right heights are reliable indicators
2. Last level nodes are left-aligned
3. Height calculations follow predictable patterns
Node values irrelevant:
Only tree structure matters, allowing focus on pointer traversal without value comparisons.

Edge Cases Implied

Empty tree (root = null) → return 0
Single node tree → return 1
Perfect binary tree (all levels full) → apply closed-form formula
Last level partially filled → need precise last-level counting

2. Intuition Scaffolding

Real-World Metaphor
Imagine a stadium with seated sections:

All upper sections are completely filled
The ground section has people seated from left to right Instead of counting each person, check if front rows are filled to deduce occupancy.

Gaming Analogy
Like exploring a dungeon where:

Each level has rooms in perfect binary arrangement
The deepest level has rooms unlocking from left to right Instead of visiting every room, check the left and right wings to estimate total rooms.

Math Analogy
Similar to finding the number of elements in a nearly-complete array where you use binary search on the “completion boundary” - the point where elements stop existing.

Common Pitfalls

Assuming complete = perfect: Last level may be partially filled
Global min/max fallacy: Checking only leftmost path gives height but not last-level occupancy
Over-traversal: Visiting every node defeats sub-linear requirement
Height miscalculation: Forgetting root height is 0 vs 1
Binary search misapplication: Incorrect mid-point calculation in last-level search

3. Approach Encyclopedia

Brute Force Approach

def countNodes(root):
    if not root:
        return 0
    return 1 + countNodes(root.left) + countNodes(root.right)

Time Complexity: $O(n)$ - visits every node exactly once
Space Complexity: $O(h)$ - recursion stack where $h$ is tree height
Visualization:

    1
   / \
  2   3
 / \  /
4  5 6

Count: 1 → 2 → 4 → 5 → 3 → 6 = 6 nodes

Optimized O(log² n) Approach

def countNodes(root):
    if not root:
        return 0
    
    # Calculate left and right heights
    left_height = get_height(root, 'left')
    right_height = get_height(root, 'right')
    
    if left_height == right_height:
        # Perfect binary tree
        return (1 << left_height) - 1
    else:
        # Last level is partially filled
        return 1 + countNodes(root.left) + countNodes(root.right)

def get_height(node, direction):
    height = 0
    while node:
        height += 1
        node = node.left if direction == 'left' else node.right
    return height

Complexity Proof:

Each recursive call does O(h) work for height calculation
Recursion depth: O(h) since we follow one path
Total: O(h) × O(h) = O(h²) = O(log² n) since h ≈ log₂n

Visualization:

    1 (h_left=3, h_right=2) → not perfect
   / \
  2   3 (h_left=2, h_right=1) → not perfect  
 / \  /
4  5 6

Left subtree: node 2 (h_left=2, h_right=2) → perfect → 3 nodes
Right subtree: node 3 → recurse

Most Optimal O(log² n) with Binary Search

def countNodes(root):
    if not root:
        return 0
    
    left_height = get_height(root.left)
    right_height = get_height(root.right)
    
    if left_height == right_height:
        # Left subtree is perfect
        return (1 << left_height) + countNodes(root.right)
    else:
        # Right subtree is perfect (one level less)
        return (1 << right_height) + countNodes(root.left)

def get_height(node):
    height = 0
    while node:
        height += 1
        node = node.left
    return height

Complexity Proof:

$T(n) = T(n/2) + O(\log n)$
By Master Theorem: $O(\log² n)$
Each step eliminates half the tree with O(log n) height check

4. Code Deep Dive

def countNodes(root: TreeNode) -> int:
    # Handle empty tree case (Example 2)
    if not root:
        return 0
    
    # Calculate left subtree height by following left pointers
    # This exploits complete tree property - left path is always longest
    left_height = get_height(root.left)
    
    # Calculate right subtree height by following left pointers
    # For complete trees, right subtree height determines last level structure
    right_height = get_height(root.right)
    
    # Case 1: Left and right heights equal
    # This means left subtree is perfect binary tree
    if left_height == right_height:
        # Left subtree has 2^left_height - 1 nodes + root + right subtree nodes
        # (1 << left_height) = 2^left_height (left subtree + root)
        return (1 << left_height) + countNodes(root.right)
    else:
        # Case 2: Left height > right height  
        # Right subtree is perfect (one level smaller)
        # Right subtree has 2^right_height - 1 nodes + root + left subtree nodes
        return (1 << right_height) + countNodes(root.left)

def get_height(node: TreeNode) -> int:
    """Calculate height by following left pointers only"""
    height = 0
    # Traverse left until null (Example 1: 1→2→4→null = height 3)
    while node:
        height += 1
        node = node.left
    return height

Edge Case Handling

Example 2 (empty): Root null check returns 0 immediately
Example 3 (single node): left_height = 0, right_height = 0 → returns (1 << 0) = 1
Example 1:
- Root: left_height=2, right_height=1 → case 2
- Returns 2 + countNodes(left)
- Left subtree: perfect → 3 + countNodes(right) = 6

5. Complexity War Room

Hardware-Aware Analysis
At maximum constraint (n = 50,000):

Height h ≈ log₂(50000) ≈ 16 levels
O(log² n) ≈ 256 operations vs O(n) = 50,000 operations
Memory: ~16 stack frames × 100 bytes ≈ 1.6KB (fits in L1 cache)

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n)	O(h)	10/10	✅ Acceptable
Height Comparison	O(log² n)	O(log n)	8/10	✅ Optimal
Binary Search	O(log² n)	O(log n)	7/10	✅ Best

6. Pro Mode Extras

Algorithm Variants

Multiple Transactions: If asked to count with limited traversals, use iterative version with stack
Streaming Trees: For trees too large for memory, use Morris traversal O(1) space
Distributed Counting: For cluster computing, adapt to map-reduce with subtree partitioning

Interview Cheat Sheet

First Mention: “For complete trees, we can exploit the structural property to achieve O(log² n)”
Key Insight: “Compare left and right subtree heights to detect perfect subtrees”
Edge Cases: “Handle empty tree and single node explicitly”
Optimization: “We can further optimize with bit manipulation for height calculation”

Advanced Optimization

def countNodes_iterative(root):
    """Iterative version avoiding recursion stack"""
    nodes = 0
    while root:
        left = get_height(root.left)
        right = get_height(root.right)
        if left == right:
            nodes += 1 << left  # 2^left
            root = root.right
        else:
            nodes += 1 << right  # 2^right  
            root = root.left
    return nodes

#222 - Count Complete Tree Nodes