DSA problem
Count Complete Tree Nodes
Given the root of a complete binary tree, return the number of nodes in the tree. A complete binary tree is one where every level except possibly the last is completely filled, and the last level has all its nodes pushed as far to the left as possible.
A naive traversal counts every node in O(n) time, which is acceptable but ignores the strong structural guarantee. The interesting variant of this problem asks for a sub-linear algorithm that exploits completeness.
The trick is that at every node we can compute, in O(log n) time, the leftmost path length and the rightmost path length. If they are equal — call them d — the subtree rooted at this node is a perfect binary tree, and its node count is exactly 2^d - 1 (or 2^d if you include the root, depending on how you define d). No further recursion is needed for that branch.
If the two depths differ, the last level is not full and we must split: the count is 1 + count(left) + count(right). Crucially, of those two recursive calls, exactly one descends into a perfect subtree and short-circuits, while only the other actually drills down. This gives the elegant recurrence T(n) = T(n/2) + O(log n), which solves to O(log² n) — a noticeable win for trees with billions of nodes.
Examples
root = [1,2,3,4,5,6]6root = []0root = [1]1Constraints
- The number of nodes in the tree is in the range [0, 5 * 10^4].
- 0 <= Node.val <= 5 * 10^4
- The tree is guaranteed to be complete.
- Follow-up: design an algorithm that runs in less than O(n) time.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.