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.
This approach leverages the property of a complete binary tree - where each level, except possibly the last, is completely filled and all nodes are as far left as possible. By loosely calculating the height from root to the leftmost leaf, and rightmost leaf, we can determine if the last level is fully filled and thus decide how to further count nodes efficiently.
The function countNodes determines the number of nodes in a complete binary tree. It calculates the height of the leftmost path and the rightmost path. If they are equal, it indicates that the tree is a full tree at this level, and the number of nodes is calculated by 2^h - 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O((log n)^2). This is because we traverse the height multiple times but reducing by the height at each recursive call.
Space Complexity: O(log n) due to the recursive stack space.
The iterative approach adapts a binary search strategy on the last level of the tree, accelerated by the properties of complete trees. It minimizes node checks by directly verifying the presence of nodes via height assessment, thereby pivoting efficiently through the binary search principle.
The code uses a combination of binary search and tree height properties to find the exact count of nodes. By binary searching the last level of the tree, where nodes might be missing, it logically narrows down potential presence of nodes swiftly.
C++
Java
Python
C#
JavaScript
Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Height Calculation | Time Complexity: |
| Approach 2: Iterative Binary Search | Time Complexity: |
| 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. |
L32. Count total Nodes in a COMPLETE Binary Tree | O(Log^2 N) Approach | C++ | Java • take U forward • 147,870 views views
Watch 9 more video solutions →Practice Count Complete Tree Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor