#222 Count Complete Tree Nodes
the problem
In plain words
The tree is complete: every level is full except maybe the last, and the last level is filled from the left with no gaps. Count its nodes — in fewer than O(n) steps.
in root = [1,2,3,4,5,6]
out 6
in root = []
out 0
in root = [1]
out 1
- 0 ≤ number of nodes ≤ 5·10⁴
- 0 ≤ Node.val ≤ 5·10⁴
- The tree is complete
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (bottom-up)Divide and conquer
where this runsJava's PriorityQueue stores its binary heap — a complete tree — in an array, finding children at 2i + 1 and 2i + 2 with no pointers at all.
Walk down the leftmost edge and the rightmost edge. Same length h → the tree is perfect and holds 2^h − 1 nodes, no counting needed. Different → count the two children the same way: one of them is always perfect, so only one branch goes deep.
solutions
From brute force to optimal
1 + count(left) + count(right). Correct for any tree — it just ignores the promise that this one is complete.
- null → 0.
- Return 1 + countNodes(left) + countNodes(right).
Visits every node once.
A complete tree is only about log₂ n levels deep.
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; return 1 + countNodes(root.left) + countNodes(root.right); // ignores the "complete" promise }}Compare the leftmost and rightmost depths; a perfect tree's size is a formula, and only the imperfect child needs more work.
- left = nodes on the path root → left → left …; right = nodes on root → right → right ….
- Equal → return (1 << left) − 1.
- Else return 1 + countNodes(root.left) + countNodes(root.right).
About log n levels of real work, each with an O(log n) edge walk; the perfect child at each level returns right after its own edge walks.
Recursion depth ≤ the tree's height.
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; int left = 0, right = 0; for (TreeNode n = root; n != null; n = n.left) left++; // levels down the left edge for (TreeNode n = root; n != null; n = n.right) right++; // levels down the right edge if (left == right) return (1 << left) - 1; // perfect: 2^h − 1 nodes, no walking return 1 + countNodes(root.left) + countNodes(root.right); // one of the two is perfect }}The last level's 2^h slots fill from the left, so binary-search for the last filled slot. A slot's bits, read from the top, say left (0) or right (1) at each level.
- h = edges down the leftmost path.
- Binary-search slot in [0, 2^h − 1]: does the walk to it end on a node?
- Answer = (2^h − 1) + (last filled slot + 1).
h ≈ log₂ n binary-search steps, each an O(h) walk from the root.
A few ints and one pointer — no recursion.
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; int h = 0; // edges from the root to the last level for (TreeNode n = root.left; n != null; n = n.left) h++; int lo = 0, hi = (1 << h) - 1; // last-level slots 0 .. 2^h − 1, filled from the left while (lo < hi) { // find the last slot that holds a node int mid = lo + (hi - lo + 1) / 2; if (exists(root, h, mid)) lo = mid; else hi = mid - 1; } return (1 << h) - 1 + lo + 1; // full levels above + nodes on the last level } /** Walks to last-level slot `slot`, reading its bits from the top: 0 = go left, 1 = go right. */ private boolean exists(TreeNode root, int h, int slot) { TreeNode node = root; for (int bit = h - 1; bit >= 0 && node != null; bit--) { node = ((slot >> bit) & 1) == 0 ? node.left : node.right; } return node != null; }}in the room
How to say it in the interview
talk track
- Give the O(n) count first, then ask: "what does complete buy us?" A perfect tree's size is a formula.
- Explain why only one branch goes deep: in a complete tree, at least one child subtree is perfect.
- State O(log² n): for n = 5·10⁴ that's a few hundred steps instead of 50,000.
traps
- Comparing full heights with a height() helper: that walks whole subtrees and is O(n) again. Walk only the outer edges.
Math.pow(2, h) - 1returns a double; use(1 << h) - 1for an exact int.- Off by one in h: 2^h − 1 needs h counted in levels (nodes on the edge), not in edges.
what they ask next
Follow-ups
Where do complete trees show up in real code?
Binary heaps: Java's PriorityQueue keeps a complete tree in a plain array, with the children of queue[i] at 2i + 1 and 2i + 2. That only works because a complete tree has no gaps.
Can you do it without recursion?
Yes — the binary search on the last level (third approach) uses O(1) extra space.
before you submit
Edge cases to test
- Empty tree → 0.
- A perfect tree (e.g. 32,767 nodes) → answered after one pair of edge walks.
- One node past perfect (32,768): the new level holds a single node on the far left.
practise next
Similar problems
- #104Maximum Depth of Binary TreeEasyin Tree Recursion
- #110Balanced Binary TreeEasyin Tree Recursion
- #704Binary SearchEasyin Binary Search