DSA Tracker

Visualize

Count Complete Tree Nodes

time O(log^2 n)space O(log n)

A complete binary tree is only missing nodes on its last level, and only from the right. That guarantee means at least one of every node's two subtrees is PERFECT (completely full) — and a perfect subtree's size is computable in O(1) from its depth via 2^depth - 1, with zero traversal needed.

Details

Animated on: Given the root of a complete binary tree [1,2,3,4,5,6], return the total number of nodes it contains.

Problem:Count Complete Tree NodesMedium

Binary Trees

step 1 / 14

4
2
5
1
6
3

Call stack

countNodes(1)

Call countNodes(1). Before counting anything, measure how deep this node's leftmost and rightmost spines go.

Pseudocode
1FUNCTION countNodes(node):
2  IF node = NULL:  RETURN 0
3  leftDepth <- length of leftmost spine from node
4  rightDepth <- length of rightmost spine from node
5  IF leftDepth = rightDepth:
6    RETURN (1 << leftDepth) - 1
7  RETURN 1 + countNodes(node.left) + countNodes(node.right)
8END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Call countNodes(1). Before counting anything, measure how deep this node's leftmost and rightmost spines go.
  2. From 1: leftDepth = 3 (following .left), rightDepth = 2 (following .right).
  3. 3 != 2, so 1 is not the root of a perfect subtree. Recurse into both children and combine.
  4. Call countNodes(2). Before counting anything, measure how deep this node's leftmost and rightmost spines go.
  5. From 2: leftDepth = 2 (following .left), rightDepth = 2 (following .right).
  6. leftDepth = rightDepth = 2, so the subtree at 2 is a PERFECT tree: 2^2 - 1 = 3 nodes, without visiting any of them.
  7. Call countNodes(3). Before counting anything, measure how deep this node's leftmost and rightmost spines go.
  8. From 3: leftDepth = 2 (following .left), rightDepth = 1 (following .right).
  9. 2 != 1, so 3 is not the root of a perfect subtree. Recurse into both children and combine.
  10. Call countNodes(6). Before counting anything, measure how deep this node's leftmost and rightmost spines go.
  11. From 6: leftDepth = 1 (following .left), rightDepth = 1 (following .right).
  12. leftDepth = rightDepth = 1, so the subtree at 6 is a PERFECT tree: 2^1 - 1 = 1 nodes, without visiting any of them.
  13. 3 combines its subtrees: 1 + 1 + 0 = 2.
  14. 1 combines its subtrees: 1 + 3 + 2 = 6. Final answer: the tree has 6 nodes total, matching the worked example.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Complete Tree Nodes in the editorAll Binary Trees problemsBack to roadmap