DSA Tracker

Visualize

Unique Binary Search Trees

G(k) = sum of G(i-1) * G(k-i) over every root choice i, memoized

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

Any value i can be the root; the BST property then forces the left subtree to hold exactly the i - 1 smaller values and the right subtree the rest, and those two counts are independent of each other. So G(k), the count for k values, is a sum over every root choice of (ways to arrange the left) times (ways to arrange the right) — and both of those are themselves smaller instances of the same problem, which is why the recursion tree keeps recomputing the SAME subproblems until memoization steps in.

Details

Animated on: n = 4 — return the number of structurally unique BSTs that store the values 1 through 4. Expected answer: 14.

Problem:Unique Binary Search TreesMedium

G(k) = sum of G(i-1) * G(k-i) over every root choice i, memoized

step 1 / 9

G(4)

Call stack

G(4)

Compute G(4): let each value i from 1 to 4 be the root in turn. Its left subtree is built from the i - 1 smaller values, its right subtree from the 4 - i larger ones — independent counts, so multiply them, then sum over every choice of i.

Pseudocode
1FUNCTION G(k):
2  IF k <= 1: RETURN 1
3  IF memo[k] exists: RETURN memo[k]
4  total <- 0
5  FOR i <- 1 TO k:
6    total <- total + G(i - 1) * G(k - i)
7  memo[k] <- total
8  RETURN memo[k]

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Compute G(4): let each value i from 1 to 4 be the root in turn. Its left subtree is built from the i - 1 smaller values, its right subtree from the 4 - i larger ones — independent counts, so multiply them, then sum over every choice of i.
  2. G(0) is the base case: zero values form exactly one arrangement, the empty tree, so it returns 1 with no recursion.
  3. Compute G(3): let each value i from 1 to 3 be the root in turn. Its left subtree is built from the i - 1 smaller values, its right subtree from the 3 - i larger ones — independent counts, so multiply them, then sum over every choice of i.
  4. Compute G(2): let each value i from 1 to 2 be the root in turn. Its left subtree is built from the i - 1 smaller values, its right subtree from the 2 - i larger ones — independent counts, so multiply them, then sum over every choice of i.
  5. G(1) is the base case: one value forms exactly one tree, so it returns 1 with no recursion.
  6. Every root choice for G(2) is in: 1×1 + 1×1 = 2. Frame pops off the stack — a later call asking for G(2) now gets 2 straight from memo, no recursion.
  7. Every root choice for G(3) is in: 1×2 + 1×1 + 2×1 = 5. Frame pops off the stack — a later call asking for G(3) now gets 5 straight from memo, no recursion.
  8. Every root choice for G(4) is in: 1×5 + 1×2 + 2×1 + 5×1 = 14. Frame pops off the stack — a later call asking for G(4) now gets 14 straight from memo, no recursion.
  9. G(4) = 14: that many structurally unique BSTs store the values 1 through 4. This is exactly the 4th Catalan number.

Now solve it yourself

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

Solve Unique Binary Search Trees in the editorAll BST problemsBack to roadmap