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 from left to right except possibly the last. A naive traversal works, but the structure of a complete tree allows faster counting.
Approach 1: Recursive Height Calculation (O(log² n) time, O(log n) space)
This approach uses the defining property of a complete tree. Compute the height of the leftmost path and the height of the rightmost path. If both heights are equal, the subtree is a perfect binary tree, and the node count is 2^h - 1. If the heights differ, recursively count nodes in the left and right subtrees. Each height calculation takes O(log n) and recursion happens across O(log n) levels, giving overall O(log² n) time with O(log n) recursion stack space.
This method avoids visiting every node. Instead, it repeatedly checks whether a subtree is perfect and skips full sections of the tree. It relies heavily on properties of binary trees and works well when you want a concise recursive solution.
Approach 2: Iterative Binary Search (O(log² n) time, O(1) space)
The last level of a complete tree may be partially filled. Treat the nodes on that level as indices from 0 to 2^h - 1. First compute the tree height by traversing the left edge. Then perform binary search over the index range of the last level to determine how many nodes exist. For each midpoint index, simulate the path from root to that node using bit decisions (left or right). Each existence check costs O(log n), and binary search runs O(log n) steps, producing O(log² n) total time.
This approach keeps memory constant and explicitly leverages the ordered structure of the last level. Bit decisions during traversal resemble operations discussed in bit manipulation, since each bit determines whether to move left or right while navigating the tree.
Recommended for interviews: The recursive height approach is the most common interview answer because it shows you recognize the structural property of complete trees and can reduce work by detecting perfect subtrees. The binary search method demonstrates deeper understanding of indexing the last level and is often considered the optimized conceptual solution.
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.
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.
Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.
We recursively traverse the entire tree and count the number of nodes.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.
For this problem, we can also take advantage of the characteristics of a complete binary tree to design a faster algorithm.
Characteristics of a complete binary tree: leaf nodes can only appear on the bottom and second-to-bottom layers, and the leaf nodes on the bottom layer are concentrated on the left side of the tree. It should be noted that a full binary tree is definitely a complete binary tree, but a complete binary tree is not necessarily a full binary tree.
If the number of layers in a full binary tree is h, then the total number of nodes is 2^h - 1.
We first count the heights of the left and right subtrees of root, denoted as left and right.
left = right, it means that the left subtree is a full binary tree, so the total number of nodes in the left subtree is 2^{left} - 1. Plus the root node, it is 2^{left}. Then we recursively count the right subtree.left > right, it means that the right subtree is a full binary tree, so the total number of nodes in the right subtree is 2^{right} - 1. Plus the root node, it is 2^{right}. Then we recursively count the left subtree.The time complexity is O(log^2 n).
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Height Calculation | Time Complexity: |
| Approach 2: Iterative Binary Search | Time Complexity: |
| Recursion | — |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Height Calculation | O(log² n) | O(log n) | Best general approach for interviews; easy to implement using recursion and subtree height checks. |
| Iterative Binary Search on Last Level | O(log² n) | O(1) | Useful when constant extra space is preferred and you want to explicitly exploit the last-level indexing of a complete tree. |
Count Complete Tree Nodes | Leetcode #222 • Techdose • 42,042 views views
Watch 9 more video solutions →Practice Count Complete Tree Nodes with our built-in code editor and test cases.
Practice on FleetCode