Watch 10 video solutions for Count Complete Tree Nodes, a easy level problem involving Binary Search, Bit Manipulation, Tree. This walkthrough by take U forward has 147,870 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[0, 5 * 104].0 <= Node.val <= 5 * 104Problem Overview: Given the root of a complete binary tree, return the total number of nodes. A complete tree fills every level except possibly the last, and the last level is filled from left to right. The key observation: complete trees have structural guarantees that let you count nodes faster than a full traversal.
Approach 1: Recursive Height Calculation (O(log^2 n) time, O(log n) space)
This method uses the structure of a binary tree to detect perfect subtrees. Compute the height of the leftmost path and the rightmost path from the current node. If both heights are equal, the subtree is perfect and contains 2^h - 1 nodes, which you can compute directly without visiting every node. If the heights differ, the subtree is not perfect, so recursively count nodes in the left and right children. Each height calculation takes O(log n), and you perform it across at most O(log n) levels of recursion.
The key insight is that a complete tree often contains large perfect subtrees. Instead of iterating through every node, the algorithm jumps over entire sections using the formula for perfect trees. Space complexity is O(log n) due to recursion depth.
Approach 2: Iterative Binary Search on Last Level (O(log^2 n) time, O(1) space)
A complete tree can be viewed like a heap-style indexed structure. First compute the tree height by walking down the left children. All levels except the last contain exactly 2^h - 1 nodes. The only unknown part is how many nodes exist on the last level.
Use binary search to determine how many nodes exist there. Treat positions in the last level as indices from 0 to 2^h - 1. For each midpoint, traverse from the root using the binary representation of the index to decide whether to move left or right. This indexing trick resembles techniques used in bit manipulation. If a node exists at that index, search the right half; otherwise search the left half.
Each existence check takes O(log n) time (tree height), and binary search runs for O(log n) iterations. The total time complexity remains O(log^2 n), but the algorithm avoids recursion and uses constant extra space.
Recommended for interviews: The recursive height comparison approach is the most commonly expected solution. It shows you understand the structural properties of complete trees and can optimize beyond a naive traversal. Mentioning the binary-search-on-last-level approach demonstrates deeper understanding of tree indexing and is a strong follow-up optimization discussion.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Height Calculation | O(log^2 n) | O(log n) | Most common interview solution. Quickly detects perfect subtrees. |
| Iterative Binary Search on Last Level | O(log^2 n) | O(1) | Useful when you want an iterative approach and constant extra memory. |
| Simple DFS Traversal | O(n) | O(h) | Baseline solution when tree properties are ignored. |