Watch 10 video solutions for Count Complete Tree Nodes, a easy level problem involving Binary Search, Bit Manipulation, Tree. This walkthrough by Techdose has 42,042 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 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.
| 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. |