Count Complete Tree Nodes
Understanding the Problem
We need to count the nodes in a complete binary tree. Traversing the whole tree and counting works, but the problem asks for a solution faster than O(n), so the structure of a complete binary tree has to carry some of the work.
What makes a complete binary tree special? Every level is fully filled except possibly the last, and the last level's nodes are packed to the left. The shape is so constrained that the height plus the position where the last level ends fully determines the count. A perfect binary tree (every level full) of height h has exactly 2^h - 1 nodes, and large chunks of a complete tree are perfect. If we can identify those perfect chunks cheaply, we can count them with the formula and only inspect the region where the last level ends.
Testing whether a subtree is perfect is cheap. Walk down its leftmost path and its rightmost path. The leftmost path always reaches the deepest level, so if the rightmost path reaches the same depth, every level in between is full and the subtree is perfect. Approach 2 turns this test into a sub-linear recursion. Approach 3 reaches the same complexity from a different angle, by binary searching for the end of the last level.
Key Constraints:
0 <= nodes <= 5 * 10^4→ An O(n) traversal would work but the problem explicitly asks for better. This points toward O(log^2 n) or O(log n) solutions.The tree is guaranteed to be complete→ This structural guarantee is the lever for sub-linear performance. We can use height comparisons to skip entire subtrees.0 nodes possible→ We must handle the empty tree case.
Approach 1: Linear Traversal (DFS)
Intuition
Ignore the completeness guarantee and count every node: visit the root, recursively count the left subtree, recursively count the right subtree, and add one for the root. This works on any binary tree, complete or not, and it is the baseline the sub-linear approaches improve on.
Algorithm
- If the root is null, return 0.
- Recursively count the nodes in the left subtree.
- Recursively count the nodes in the right subtree.
- Return left count + right count + 1 (for the current node).
Example Walkthrough
Input:
The recursion visits all six nodes. The leaves resolve first: countNodes(4), countNodes(5), and countNodes(6) each return 1 + 0 + 0 = 1, since both of their children are null. Then the results combine on the way back up: node 2 returns 1 + 1 + 1 = 3, node 3 returns 1 + 1 + 0 = 2 (its right child is null), and the root returns 1 + 3 + 2 = 6.
Code
- Time Complexity: O(n). We visit every node exactly once, doing O(1) work at each node.
- Space Complexity: O(log n). The recursion stack goes as deep as the tree height, and the tree is guaranteed complete, so h = O(log n). For a general binary tree this would be O(n) in the worst case.
This counts correctly but touches all n nodes and never uses the completeness guarantee. The next approach detects perfect subtrees and replaces their traversal with the 2^h - 1 formula.
Approach 2: Recursive Height Comparison
Intuition
In a complete binary tree, a subtree is perfect exactly when its leftmost depth equals its rightmost depth. The leftmost path always reaches the deepest level, so if the rightmost path goes equally deep, every level in between is full. Both depths cost O(log n) to compute: walk down-left, then walk down-right.
That gives the algorithm: at each node, compare the two depths. If they match, return 2^h - 1 without touching the interior of the subtree. If they differ, count the node itself and recurse into both children.
Recursing into both children sounds like it could degenerate back to visiting everything, but it cannot. The last level fills left to right, so at any node where the depths differ, one child's subtree is perfect: either the left child is perfect at full height (the last level extends into the right child), or the right child is perfect one level shorter (the last level ends inside the left child). The perfect child's two depths match, so its call returns by formula without recursing further. Only one branch keeps going, which bounds the recursion at O(log n) levels with O(log n) depth computation per level, for O(log^2 n) total.
Algorithm
- If the root is null, return 0.
- Compute the left depth by walking down-left from the root until reaching null.
- Compute the right depth by walking down-right from the root until reaching null.
- If left depth equals right depth, the tree is perfect. Return 2^leftDepth - 1.
- Otherwise, recurse: return 1 + countNodes(left child) + countNodes(right child).
Example Walkthrough
Code
- Time Complexity: O(log^2 n). We recurse O(log n) times (the height of the tree). At each recursive call, we compute the left and right depths, each taking O(log n) time. Total: O(log n) * O(log n) = O(log^2 n).
- Space Complexity: O(log n). The recursion depth equals the height of the tree, which is O(log n) for a complete binary tree.
This meets the sub-linear target but keeps O(log n) recursion frames on the stack. The next approach reaches the same O(log^2 n) time iteratively, in O(1) space, by treating the last level as a search range.
Approach 3: Binary Search on the Last Level
Intuition
A complete binary tree of height h (counting the root level as height 1) has its first h-1 levels fully filled, which accounts for 2^(h-1) - 1 nodes. The only unknown is how many nodes sit on the last level, somewhere between 1 and 2^(h-1). Count those, and the answer follows by addition.
Label the last-level positions 0 through 2^(h-1) - 1 from left to right. Because the level fills from the left, the occupied positions form a prefix: every position up to some index k holds a node, and every position after k is empty. A monotonic boundary like this is what binary search finds. Search for k, and the answer is (2^(h-1) - 1) + (k + 1).
Checking whether a given position holds a node takes one root-to-leaf walk. The left half of the position range lives under the left child and the right half under the right child, so at each level we narrow the range to the half containing the target and step into the matching child. Each check costs O(log n). Approach 2 performs this same pruning implicitly through depth comparisons; this version makes the binary search explicit and removes the recursion.
Binary search needs a valid starting bracket and a monotonic predicate, and the tree shape provides both. Position 0 always holds a node: the height was measured down the leftmost path, so the leftmost slot of the last level exists whenever h > 1. The left-filling rule guarantees that nodeExists is true for every position up to the boundary k and false after it, which is the monotonicity the search relies on.
The midpoint rounds up (low + (high - low + 1) / 2) because a successful check assigns low = mid. With a rounded-down midpoint, low = mid would make no progress when high == low + 1 and the loop would never terminate.
Algorithm
- Compute the height h of the tree by walking down-left.
- If h is 1, the tree has only the root. Return 1.
- The last level can hold up to 2^(h-1) nodes (positions 0 to 2^(h-1) - 1, using 0-indexed).
- Binary search for the rightmost position on the last level that has a node.
- For each candidate position, trace from the root to that position: at level i, go left if the position is in the left half, right otherwise.
- The total node count is 2^(h-1) - 1 (nodes above last level) + number of nodes on last level.
Example Walkthrough
Code
- Time Complexity: O(log^2 n). Binary search on the last level does O(log n) iterations. Each iteration calls nodeExists, which traverses O(log n) levels. Total: O(log n) * O(log n) = O(log^2 n).
- Space Complexity: O(1). Only uses a constant number of variables. No recursion stack needed (the nodeExists traversal is iterative).