Count the number of nodes in a complete binary tree efficiently.
Given the root of a complete binary tree, return the total number of nodes in the tree.
A complete binary tree is a binary tree in which every level is completely filled except possibly the last, and all nodes in the last level are as far left as possible.
A naive traversal works, but the intended challenge is to do better than visiting every node when possible by using the structure of the tree.
Input Format
- A binary tree root node is provided as the input.
- Each node contains an integer value, but the values are irrelevant to the count.
Output Format
Return an integer representing the total number of nodes in the tree.
Constraints
- The tree is a complete binary tree.
- The tree may be empty.
- Node values are not important for the answer.
Example 1
Input
root = [1,2,3,4,5,6]
Output
6
Explanation
The tree has 6 nodes in total.
Example 2
Input
root = []
Output
0
Explanation
An empty tree has no nodes.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.