Pattern visualizer

Count Total Nodes in Complete Binary Tree

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. Animated on: Given the root of a complete binary tree [1,2,3,4,5,6], return the total number of nodes it contains..

Binary Trees

time O(log^2 n)space O(log n)step 1 / 14

Call stack

countNodes(1)

line 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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap