Count the Nodes of a Complete Tree Without Visiting Them All
Solve this ProblemYou are given the root of a complete binary tree: every level except possibly the last is completely filled, and the last level's nodes are packed as far left as possible. Return the number of nodes in the tree.
Counting the nodes one by one takes O(n) time. Because the tree is complete, you can do better: a subtree whose left edge and right edge have the same number of nodes is completely full, and its size follows directly from its height.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 5000; 1 ≤ node.val ≤ 90 (the values themselves never affect the answer) - ◆
The tree is complete: every level except possibly the last is completely filled, and the nodes of the last level sit as far to the left as possible - ◆
Return how many nodes the tree has - ◆
A solution faster than O(n) is expected: it should take fewer than n steps by using the complete-tree shape
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Visit and Count Every Node
BruteIgnore the special shape: the size of a tree is 1 (this node) plus the size of its left subtree plus the size of its right subtree, and an empty tree has size 0. This visits every node once, so it takes O(n) time; the recursion is only as deep as the tree is tall, and a complete tree has height about log n. Correct, but it does not take advantage of being complete.
O(n)O(log n)1class Solution {
2 public int countNodes(TreeNode root) {
3 if (root == null) return 0;
4 return 1 + countNodes(root.left) + countNodes(root.right);
5 }
6}Optimal — Compare the Left and Right Edge Heights
OptimalIn a complete tree, walk down the leftmost edge counting nodes (lh) and down the rightmost edge counting nodes (rh). If they are equal, the tree is full — every level completely filled — so it has exactly 2^lh − 1 nodes and no visiting is needed. If they differ, count this node plus the two subtrees recursively. At most one of the two subtrees can be non-full (the other is always full), so the recursion follows a single path down the tree: about log n levels, each costing an O(log n) edge walk — O(log² n) total, far below O(n).
O(log² n)O(log n)1class Solution {
2 public int countNodes(TreeNode root) {
3 if (root == null) return 0;
4 int lh = 0, rh = 0;
5 TreeNode l = root, r = root;
6 while (l != null) {
7 lh++;
8 l = l.left;
9 }
10 while (r != null) {
11 rh++;
12 r = r.right;
13 }
14 if (lh == rh) return (1 << lh) - 1;
15 return 1 + countNodes(root.left) + countNodes(root.right);
16 }
17}