AlgoVerse

Counting binary trees (recursive)

Count the binary trees with n nodes straight from the recursive definition; the call tree shows why the dynamic-programming version (Catalan numbers) is better.

Describe a binary tree with n nodes by its root and its subtrees. If the left subtree has i nodes, the right one has n − 1 − i, and every pair of subtrees makes a new tree:

Read the full explanation ↓
Input:
n=3PDF export

3 nodes: 5 trees (2 + 1 + 2, depending on how many nodes are on the root's left).

  1. def count_trees(n):
  2. # The number of binary trees with n nodes: the root, then i nodes on the left and n − 1 − i on the right.
  3. if n <= 1:
  4. return 1
  5. total = 0
  6. for left in range(n):
  7. right = n - 1 - left
  8. total = total + count_trees(left) * count_trees(right)
  9. return total

Invariant: Every tree with n nodes is counted exactly once: by the size of its left subtree.

Start

n3
left—
right—
total—

Recursion tree

3

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

n3

Orange = changed in this step

Call stack

  1. count_trees()line 1
Step 1 of 72
Black = count · Orange = key stepbase: 0/12 · split: 0/7 · count: 0/3
    Explanation

    The idea

    Describe a binary tree with n nodes by its root and its subtrees. If the left subtree has i nodes, the right one has n − 1 − i, and every pair of subtrees makes a new tree:

    T(n) = Σ T(i) · T(n − 1 − i)   for i = 0 … n − 1,   T(0) = T(1) = 1

    The answers are the Catalan numbers: 1, 1, 2, 5, 14, 42, …

    Why it is slow

    Each call calls several smaller subproblems, and the same subproblems are computed again and again; the number of calls is exponential. The dynamic-programming version (the "Catalan numbers" page) computes each T(k) once: O(n²).

    What to watch in the trace

    • Look at the call tree: nodes with the same n repeat many times.