LeetCode 222 - Count Complete Tree Nodes

Difficulty: 🟢 Easy
Topics: Binary Search, Bit Manipulation, Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to count how many nodes exist in a complete binary tree. A complete binary tree has a very specific structure. Every level except possibly the last one is completely filled, and the nodes on the final level appear as far left as possible.

The input is the root node of a binary tree. Each node contains a value and pointers to its left and right children. The output should be a single integer representing the total number of nodes in the tree.

A naive solution would simply traverse every node and count them. While that works correctly, the problem explicitly asks for an algorithm faster than O(n). This requirement is important because it signals that the complete tree property can be exploited to avoid visiting every node individually.

The constraints allow up to 5 * 10^4 nodes, which is not extremely large, but still large enough that the interviewer expects an optimized solution. Since the tree is guaranteed to be complete, we can take advantage of structural properties that are not available in arbitrary binary trees.

There are several important edge cases to consider:

The tree may be empty, meaning root = None. In that case, the answer is 0.
The tree may contain only one node. The algorithm must correctly identify this smallest non-empty case.
The last level may be partially filled. This is where most bugs occur because the tree is not necessarily perfect.
Some subtrees inside the complete tree may themselves be perfect binary trees. Detecting this efficiently is the key optimization.

Approaches

Brute Force Approach

The simplest solution is to traverse the entire tree and count every node manually. This can be done using either depth-first search or breadth-first search.

For example, with DFS:

Count the current node as 1
Recursively count nodes in the left subtree
Recursively count nodes in the right subtree
Return the total

This works because every node is visited exactly once, so the final count is accurate.

However, this approach requires visiting all n nodes, giving a time complexity of O(n). The problem specifically asks for a solution faster than linear time, so while the brute-force solution is correct, it does not satisfy the optimization requirement.

Optimal Approach

The key insight comes from the properties of a complete binary tree.

In a perfect binary tree:

Every level is completely filled
The number of nodes is:

$2^h-1$

where h is the height of the tree.

For any subtree in a complete binary tree, we can determine whether it is perfect by comparing:

The height obtained by continuously moving left
The height obtained by continuously moving right

If both heights are equal, the subtree is perfect, so we can compute its node count instantly using the formula above instead of traversing every node.

If the heights differ, the subtree is not perfect, so we recursively count nodes in the left and right subtrees.

This dramatically reduces the number of nodes we need to inspect.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	`O(n)`	`O(h)`	Traverses every node
Optimal	`O(log^2 n)`	`O(log n)`	Uses complete tree structure and subtree height checks

Algorithm Walkthrough

Start at the root node of the tree. If the root is None, return 0 immediately because the tree is empty.
Compute the left height by repeatedly following the left child until reaching None. Count how many levels were traversed.
Compute the right height by repeatedly following the right child until reaching None.
Compare the two heights:

If the heights are equal, the subtree is perfect.
A perfect binary tree with height h contains:

$2^h-1$

nodes, so return this value directly.

If the heights are different, the subtree is not perfect. In this case:

Recursively count nodes in the left subtree
Recursively count nodes in the right subtree
Add 1 for the current root node

Continue recursively until all necessary subtrees have been processed.

Why it works

The algorithm relies on a fundamental property of complete binary trees. If the leftmost path height equals the rightmost path height, the subtree must be perfect. A perfect binary tree has a known closed-form node count, allowing us to avoid traversing all nodes inside it.

If the heights differ, at least one subtree is incomplete, so recursion is required. Because each recursive call reduces the tree height and each height computation takes O(log n), the total runtime becomes O(log^2 n).

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        
        def left_height(node: Optional[TreeNode]) -> int:
            height = 0
            
            while node:
                height += 1
                node = node.left
            
            return height
        
        def right_height(node: Optional[TreeNode]) -> int:
            height = 0
            
            while node:
                height += 1
                node = node.right
            
            return height
        
        if not root:
            return 0
        
        left_h = left_height(root)
        right_h = right_height(root)
        
        if left_h == right_h:
            return (1 << left_h) - 1
        
        return (
            1
            + self.countNodes(root.left)
            + self.countNodes(root.right)
        )

The implementation begins by defining two helper functions:

left_height() computes the height by continuously traversing left children.
right_height() computes the height by continuously traversing right children.

These helper functions are used to determine whether the current subtree is perfect.

If the heights match, the subtree is perfect, so the node count is calculated directly using bit manipulation:

(1 << height) - 1

This expression computes:

$2^h-1$

efficiently.

If the heights differ, the subtree is incomplete. The algorithm recursively counts nodes in the left and right subtrees and adds 1 for the current node.

Because complete trees contain many perfect subtrees, the algorithm avoids traversing large portions of the tree explicitly.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func countNodes(root *TreeNode) int {
    
    var leftHeight func(*TreeNode) int
    leftHeight = func(node *TreeNode) int {
        height := 0
        
        for node != nil {
            height++
            node = node.Left
        }
        
        return height
    }
    
    var rightHeight func(*TreeNode) int
    rightHeight = func(node *TreeNode) int {
        height := 0
        
        for node != nil {
            height++
            node = node.Right
        }
        
        return height
    }
    
    if root == nil {
        return 0
    }
    
    leftH := leftHeight(root)
    rightH := rightHeight(root)
    
    if leftH == rightH {
        return (1 << leftH) - 1
    }
    
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

The Go implementation follows the same logic as the Python version.

The primary difference is how helper functions are declared. Go uses function variables with closures because nested named functions are not supported directly.

The algorithm uses nil checks instead of Python's None.

Bit shifting is also used in Go to compute:

$2^h-1$

efficiently.

Since the maximum number of nodes is only 5 * 10^4, integer overflow is not a concern with Go's standard int type.

Worked Examples

Example 1

Input:

root = [1,2,3,4,5,6]

Tree structure:

At the root:

Step	Left Height	Right Height	Action
Root = 1	3	2	Not perfect, recurse

Now process left subtree rooted at 2:

Step	Left Height	Right Height	Action
Root = 2	2	2	Perfect subtree

Node count:

$2^2-1=3$

Now process right subtree rooted at 3:

Step	Left Height	Right Height	Action
Root = 3	2	1	Not perfect

Process subtree rooted at 6:

Step	Left Height	Right Height	Action
Root = 6	1	1	Perfect

Count:

1 + 3 + 2 = 6

Final answer:

Example 2

Input:

root = []

The root is None.

Step	Action
Check root	Root is empty
Return	0

Final answer:

Example 3

Input:

root = [1]

Step	Left Height	Right Height	Action
Root = 1	1	1	Perfect subtree

Count:

$2^1-1=1$

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(log^2 n)`	Each recursive level computes heights in `O(log n)` time
Space	`O(log n)`	Recursive call stack height

The tree height of a complete binary tree is O(log n). At each recursive step, the algorithm computes the left and right heights, each requiring O(log n) work.

Since recursion also occurs over at most O(log n) levels, the total runtime becomes:

$O(\log n \cdot \log n)=O(\log^2 n)$

The space complexity comes entirely from recursion depth, which is bounded by the tree height.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

s = Solution()

# Empty tree
assert s.countNodes(None) == 0  # tests empty input

# Single node
root = TreeNode(1)
assert s.countNodes(root) == 1  # tests smallest non-empty tree

# Perfect binary tree with 3 levels
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(
        3,
        TreeNode(6),
        TreeNode(7)
    )
)
assert s.countNodes(root) == 7  # tests perfect tree optimization

# Complete but not perfect
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(
        3,
        TreeNode(6),
        None
    )
)
assert s.countNodes(root) == 6  # tests incomplete last level

# Two-node tree
root = TreeNode(
    1,
    TreeNode(2),
    None
)
assert s.countNodes(root) == 2  # tests minimal incomplete tree

# Left-heavy final level
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(4),
        None
    ),
    TreeNode(3)
)
assert s.countNodes(root) == 4  # tests partially filled last level

# Larger complete tree
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(
        3,
        TreeNode(6),
        TreeNode(7)
    )
)
root.left.left.left = TreeNode(8)
root.left.left.right = TreeNode(9)

assert s.countNodes(root) == 9  # tests deeper recursion

Test	Why
Empty tree	Validates handling of `None` root
Single node	Verifies smallest valid tree
Perfect binary tree	Ensures optimization path works
Complete but not perfect	Tests recursive subdivision
Two-node tree	Checks partial final level
Left-heavy final level	Validates completeness assumptions
Larger complete tree	Tests deeper recursive structure

Edge Cases

Empty Tree

An empty tree is represented by root = None. This case is easy to overlook when writing recursive logic because attempting to access child pointers on None would cause runtime errors.

The implementation handles this immediately with:

if not root:
    return 0

This guarantees safe execution for empty input.

Single Node Tree

A tree containing only one node is the smallest non-empty valid input. In this case, both the left height and right height are 1, meaning the subtree is perfect.

The algorithm correctly computes:

$2^1-1=1$

without any recursive calls.

Incomplete Final Level

The most important edge case is when the final level is only partially filled. This is the defining characteristic of a complete binary tree.

For example:

The root subtree is not perfect because the left and right heights differ. A buggy implementation might incorrectly assume completeness implies perfection.

This implementation avoids that mistake by explicitly comparing leftmost and rightmost heights at every subtree before deciding whether to apply the perfect-tree formula.

Deep Perfect Subtrees

A complete tree often contains large perfect subtrees nested inside an incomplete overall tree. Efficient handling of these cases is the reason the optimized algorithm works.

For example, even if the entire tree is not perfect, the left subtree may still be perfect. The algorithm detects this instantly and computes its node count in constant time after height calculation, avoiding unnecessary traversal of all descendant nodes.