Pattern visualizer
Unique Binary Search Trees
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. Animated on: n = 4 — return the number of structurally unique BSTs that store the values 1 through 4. Expected answer: 14..
G(k) = sum of G(i-1) * G(k-i) over every root choice i, memoized
Call stack
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.
1FUNCTION G(k):2 IF k <= 1: RETURN 13 IF memo[k] exists: RETURN memo[k]4 total <- 05 FOR i <- 1 TO k:6 total <- total + G(i - 1) * G(k - i)7 memo[k] <- total8 RETURN memo[k]
← / → step · space play · Home restart