Count Complete Tree Nodes

Medium#222tree nodes

You get the root of a complete binary tree: every level is full except maybe the last, and the last one is filled from the left. Count its nodes faster than by visiting each one. Our tree has 4 levels: the first three are full, and the last holds 5 nodes out of 8 — the answer is 12.

222 Count Complete Tree NodesWalkthrough · 1×

Example: count the nodes of a complete binary tree: where the left and right edges are the same length, the subtree is perfect and its count is known at once.

123456789101112call stacktop on the right1
not counted yetwaiting on the call stackcurrent callthe edge being walkedcounted, ↑ what its call returned

1 is a node, not none

01/38
restart · back · play · step
Speed
1function countNodes(node):
2 if node is none:
3 return 0
4 hl = nodes down the left edge from node
5 hr = nodes down the right edge from node
6 if hl == hr:
7 return 2^hl - 1 // perfect: no need to go inside
8 return 1 + countNodes(node.left) + countNodes(node.right)
state
node
1
hl
–
hr
–
click a step to go back

← → step · space play/pause

Why it works

  1. In a complete tree the last level fills from the left. If the leftmost and the rightmost paths are the same length, that level is full too, and a perfect tree of h levels has 2^h − 1 nodes.
  2. If they differ, at least one of the two subtrees is perfect, so one of the two calls answers at once from its edges. Only one path down is ever counted the long way.

Complexity

Time O(log² n): the long way goes down one path of O(log n) calls, and each call walks two edges of O(log n) nodes. Memory O(log n) for the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.