Count Complete Tree Nodes: Binary Search on a Tree

You are given the root of a complete binary tree and need to return the total number of nodes. A complete binary tree has every level fully filled except possibly the last, where nodes are packed as far left as possible. The naive O(n) traversal works, but you can do better by exploiting the structure of completeness. This is LeetCode 222: Count Complete Tree Nodes.

Using tree height to skip subtrees

The key insight is that in a complete binary tree, at least one of the two subtrees at any node is a perfect binary tree. A perfect binary tree of height h has exactly 2^h - 1 nodes, so you can count an entire subtree in O(1) instead of visiting every node.

Here is how you detect it. At each node, walk all the way down the left side to measure the left height, and walk all the way down the right side to measure the right height. If they match, the tree rooted at that node is perfect, and you return 2^(h+1) - 1. If they do not match, the tree is not perfect at this level, so you recurse into both children and add 1 for the current node.

Because a complete tree is always "nearly balanced," one of the two recursive calls will immediately hit the perfect-tree shortcut. This means you only recurse O(log n) times, and each recursion does O(log n) work to measure heights. The total time is O(log^2 n).

The solution

def count_nodes(root):
    if not root:
        return 0

    left_height = 0
    node = root
    while node.left:
        left_height += 1
        node = node.left

    right_height = 0
    node = root
    while node.right:
        right_height += 1
        node = node.right

    if left_height == right_height:
        return (1 << (left_height + 1)) - 1

    return 1 + count_nodes(root.left) + count_nodes(root.right)

1. Base case: if root is None, there are zero nodes.
2. Measure left height: starting from the root, follow .left pointers all the way down. Count the edges (not nodes), so a single node has left height 0.
3. Measure right height: same idea, but follow .right pointers all the way down.
4. Perfect tree check: if left height equals right height, every level is full. The node count is 2^(h+1) - 1, computed with a bit shift for speed.
5. Recurse: if heights differ, count the current node (1) plus the counts from both subtrees.

Step-by-step walkthrough

Let's trace through a complete binary tree with nodes [1, 2, 3, 4, 5, 6]. The last level is not completely filled (node 3 is missing its right child), so the algorithm will recurse at the root but will hit the perfect-tree shortcut on the left subtree.

Notice how the left subtree rooted at node 2 was counted instantly because its left and right heights matched. We never visited nodes 4 or 5 individually. That is where the logarithmic speedup comes from.

Complexity analysis

Building blocks

1. Height measurement by walking one side. Measuring the height of a complete tree by following only .left or only .right is a pattern you will reuse in any problem that exploits tree shape. The core loop is simple:

h = 0
node = root
while node.left:
    h += 1
    node = node.left

2. Perfect binary tree shortcut. When you know a subtree is perfect, you can compute its node count with 2^(h+1) - 1 in O(1). This avoids traversing the entire subtree and is the foundation of the logarithmic speedup. Use a bit shift (1 << (h + 1)) to compute the power of two efficiently.

3. Binary search on tree structure. The recursive split at each node is essentially a binary search. You check whether the left subtree is perfect. If it is, the "missing" nodes are in the right subtree, so you recurse right. If it is not, you recurse left. Either way, you eliminate roughly half the tree at each step, just like binary search on an array.

Edge cases

• Empty tree: root is None, return 0. The base case handles this directly.
• Single node: left height and right height are both 0. The tree is perfect with 2^1 - 1 = 1 node.
• Perfect binary tree: left and right heights match at the root, so the answer is computed in a single O(log n) height measurement with no recursion needed.
• Last level has only one node: the tree is maximally unbalanced for a complete tree. The algorithm still runs in O(log^2 n) because each recursive call reduces the problem by half.
• Very large trees (n in the millions): the O(log^2 n) solution is dramatically faster than O(n). For n = 1,000,000, you do roughly 20 * 20 = 400 operations instead of 1,000,000.

From understanding to recall

You now see why comparing left and right heights lets you skip entire subtrees. The complete tree guarantee ensures that at least one subtree is always perfect, giving you the logarithmic elimination at each level. The code is short, but the insight behind it is what matters.

In an interview, will you remember to measure height by walking one side instead of doing a full DFS? Will you remember the 2^(h+1) - 1 formula and the bit shift trick? Or will you default to a simple O(n) traversal because the height-based approach slipped away?

Spaced repetition closes that gap. You practice writing the solution from scratch at increasing intervals. Each time, you reconstruct the height measurement loops, the equality check, and the recursive fallback. After a few rounds, the pattern is automatic.

Related problems

• Balanced Binary Tree uses bottom-up height computation on trees, the same height measurement skill applied to a validation problem
• Maximum Depth of Binary Tree is the foundation for measuring tree height, which this problem builds on directly
• Binary Search Pattern covers the general binary search idea that this problem applies to tree structure instead of arrays