Problem Statement
Count Complete Tree Nodes
You are given the top node (the root) of a complete binary tree, and you need to return how many nodes are in it. A binary tree is a structure where each node can have a left child and a right child. Complete means the tree fills up neatly: every level is full except maybe the last one, and the bottom level is packed in from the left with no gaps. The easy way to count is to visit every node, but that takes one step per node. We can do much better by using the fact that the tree is so tidy.
Signals to notice
Brute force first
Visit every node and count. Ignores the complete tree structure entirely. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
Compare left and right subtree heights. If equal, the left subtree is perfect — its count is 2^h - 1. Recurse on right. If unequal, the right subtree is perfect at one level shorter. Recurse on left. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on root=[1,2,3,4,5,6] (3 has only a left child = 6)
count(1): lh(left=2)=2 [2->4], rh(right=3)=2 [3->6]; equal => left subtree perfect, ans += 1<<2 = 4, recurse right=3 count(3): lh(left=6)=1, rh(right=null)=0; unequal => right subtree perfect, ans += 1<<0 = 1, recurse left=6 count(6): lh(null)=0, rh(null)=0; equal => ans += 1<<0 = 1, recurse right=null count(null): return 0 Unwind: count(6)=1+0=1; count(3)=1+1=2; count(1)=4+2=6 return 6
What must stay true
In a complete binary tree, at least one subtree is always a perfect binary tree. A perfect tree of height h has exactly 2^h - 1 nodes — no need to traverse it. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
count(node):
if node is null: return 0
lh = leftHeight(node.left); rh = leftHeight(node.right)
if lh == rh: # left subtree perfect
return (1 << lh) + count(node.right)
else: # right subtree perfect
return (1 << rh) + count(node.left)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Computing height by traversing the whole subtree — in a complete tree, height = number of left-most children. per height check. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.