mediumTreesPure DSA~30 min
Count Nodes in a Complete Binary Tree Faster Than O(n)
Count the nodes of a complete binary tree, exploiting completeness to beat a full traversal.
Problem
Given the root of a complete binary tree, return the number of nodes. A complete tree has every level full except possibly the last, which is filled left to right. Aim for better than O(n).
Input
A complete binary tree root.
Output
An integer: the node count.
Constraints
- 0 <= number of nodes <= 5*10^4
- The tree is complete.
- Target complexity is O(log^2 n).
Examples
Example 1
Input
root = [1,2,3,4,5,6]
Output
6
Six nodes total.
Example 2
Input
root = []
Output
0
An empty tree.