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 * 104The key observation in #222 Count Complete Tree Nodes is that the tree is complete, meaning all levels are filled except possibly the last, and nodes are as far left as possible. This property allows a faster solution than traversing every node.
A common strategy is to compare the leftmost depth and rightmost depth of a subtree. If both depths are equal, the subtree is a perfect binary tree and the number of nodes can be computed directly using 2^h - 1. Otherwise, recursively count nodes in the left and right subtrees.
Another optimized idea is to treat the last level like a search space and use binary search to determine how many nodes exist there. By checking whether a node exists at a specific index using tree traversal, you can efficiently determine the final count.
This reduces the complexity significantly compared to a full traversal while leveraging the structural guarantees of complete binary trees.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Simple DFS/BFS Traversal | O(n) | O(h) |
| Height Comparison / Binary Search on Last Level | O((log n)^2) | O(log n) |
take U forward
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.
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.
1var countNodes = function(root) {
2 let leftHeight = function(node) {
3 let h = 0;
4
The JavaScript solution computes the height for the leftmost and rightmost paths for recognizing perfect binary trees, applying recursive logic for imbalanced subtrees.
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.
Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar variations appear in technical interviews at major companies. It tests understanding of binary tree properties, recursion, and optimization using structural insights.
The problem uses a binary tree data structure, specifically a complete binary tree. Efficient solutions rely on tree height calculations, recursion, and sometimes binary search on the last level.
Binary search can be applied to the last level of the complete tree because nodes are filled from left to right. By checking whether nodes exist at specific positions, you can determine how many nodes exist without scanning the entire level.
The optimal approach leverages the properties of a complete binary tree. By comparing the leftmost and rightmost heights of a subtree, you can quickly detect perfect subtrees and compute their node counts using a formula instead of traversing every node.
By executing a binary search over potential nodes in the last row of a binary tree, the Python solution establishes a balance of control over tree enumeration.