Count Complete Tree Nodes
Medium · Trees · Binary Search · Bit Manipulation · Tree · Binary Tree
Problem
Given the root of a complete binary tree, return the number of nodes in it.
In a complete binary tree every level is completely filled except possibly the last, and the last level's nodes are packed as far left as possible. If the last level is level h (the root is level 0), it holds between 1 and 2^h nodes.
Design an algorithm that runs in less than O(n) time.
Examples
Input: root = [1,2,3,4,5,6,7,8,9,10] Output: 10
The first three levels are full (7 nodes) and the last level holds 3 more.
Input: root = [] Output: 0
The tree is empty.
Constraints
- The number of nodes is in the range [0, 5 · 10^4]
- 0 <= Node.val <= 5 · 10^4
- The tree is guaranteed to be complete
Approaches
- Baseline: visit every node — time O(n), space O(log n)
Follow-up
Heaps store complete trees in arrays, where position p has children 2p and 2p + 1; the binary-search solution is that numbering in disguise. The use cases spell out the path to a numbered position, and check whether a tree really is complete before trusting a fast count.
Related problems
Start free on Cariara · Coding problems · System design studio
