Count total nodes in a complete BT
EasyA perfect subtree can be counted by formula
Problem
Count the nodes of a complete binary tree faster than O(n).
In a complete tree you can count via left/right heights in log-squared time instead of visiting all.
The idea
Measure the leftmost and rightmost depths of a subtree; if they are equal the subtree is perfect and holds 2^depth - 1 nodes with no traversal needed. Otherwise recurse into both children, which gives O(log² n).
The trick
- Equal left and right spines mean perfect — use the formula.
- Only one branch is ever imperfect at each level, so the recursion is shallow.
- O(log² n), far better than counting every node.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,3,4,5,6] Values: 1, 2, 3, 4, 5, 6.
1lh = leftHeight; rh = rightHeight2if lh==rh: return 2^lh - 13return 1 + count(left) + count(right)Input
- array
- [1, 2, 3, 4, 5, 6]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,3,4,5,6]
- Output:
- 6
- Explanation:
- Six nodes total.
Example 2
- Input:
- tree = [1]
- Output:
- 1
- Explanation:
- One node.
Example 3
- Input:
- tree = []
- Output:
- 0
- Explanation:
- Empty → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.