Description
Given the root of a complete binary tree, return the number of nodes in the tree. Design an algorithm that runs in less than O(n) time complexity.
Examples
Input:
root = [1,2,3,4,5,6]Output:
6Explanation:
Complete binary tree with root 1, children 2,3, and grandchildren 4,5,6. Use binary search on last level for O(log²n).
Input:
root = []Output:
0Explanation:
An empty tree has no nodes, so the count is 0.
Input:
root = [1,2,3,4,5,6,7,8,9,10,11]Output:
11Explanation:
This complete binary tree has 4 levels. The first 3 levels are completely filled (nodes 1-7), and the last level has 4 nodes (8-11) filled from left to right, totaling 11 nodes.
Constraints
- •
0 ≤ number of nodes ≤ 5 * 10⁴ - •
The tree is a complete binary tree