Count Complete Tree Nodes
Given the root of a complete binary tree, return the total number of nodes in the tree.
A complete binary tree is a tree where:
- Every level is completely filled except possibly the last level.
- The nodes in the last level are filled from left to right.
Example:
1
/ \
2 3
/ \ /
4 5 6
The tree contains:
6 nodes
So the answer is:
6
Important Idea
A simple traversal can count every node in O(n).
But because the tree is complete, we can do better by checking the height of the left and right subtrees.
Example 1
Input
root = [1,2,3,4,5,6]
Output
6
Explanation
The tree is:
1
/ \
2 3
/ \ /
4 5 6
Counting the nodes:
1 → 1 node
2, 3 → 2 nodes
4, 5, 6 → 3 nodes
Therefore:
1 + 2 + 3 = 6
So the answer is:
6
Example 2
Input
root = []
Output
0
Explanation
The tree is empty, so it contains no nodes.
Therefore, the answer is:
0
Constraints
Hints:
Hint 1
The straightforward solution is to perform DFS or BFS and count every node.
Hint 2
Can you use the fact that the tree is complete?
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 15, 2026
Last updated
Aug 15, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output