The O(n) Club: Unique Binary Search Trees—Or, Why Catalan Numbers Rule the Forest

The O(n) Club: Unique Binary Search Trees—Or, Why Catalan Numbers Rule the Forest

⚡ TL;DR

Want to know how many different BSTs you can make from 1 to n? It’s not about permutations—it’s all about unique shapes, which just so happen to follow the Catalan numbers. Bruteforce is a crime against your CPU, so here’s dynamic programming for the win:

// Brute force—only use if you like stack overflows!
int numTrees(int n) {
    if (n == 0 || n == 1) return 1;
    int total = 0;
    for (int root = 1; root <= n; ++root)
        total += numTrees(root - 1) * numTrees(n - root);
    return total;
}

🧠 How Devs Usually Mess This Up

Let’s be honest, we all have that first impulse to count every possible permutation of values 1…n and pat ourselves on the back. But actually, unique BSTs care about structure, not the numbers. If you ignore that, you’ll overshoot the answer faster than a junior dev on their first caffeine binge.

Also, lots of folks think subtrees combine by addition, not multiplication. But guess what? It’s combinations, not options. Each left subtree pairs with each right subtree: product not sum, my friend!

And—pro tip—don’t forget the base case for size 0 and 1. If you skip it, your DP table will look as sad as a Monday morning standup.

🔍 What’s Actually Going On

Imagine you’ve got n weird Lego bricks. For every choice of root (say, picking brick i), you split the rest into two randomly sized heaps: the ones smaller than i (left subtree), and the ones bigger than i (right subtree). Every arrangement of the left combines with every arrangement on the right, for every possible root. The end result: all the unique BSTs you can build.

Cue the Catalan numbers—the same folks behind correctly matched parentheses, polygon triangulation, and nightmares about recursion.

🛠️ PseudoCode

• Create a DP array: int[] numTrees = new int[n + 1];
  • Where numTrees[k] will store: number of unique BSTs for k nodes.
• Base Cases: numTrees[0]=1; and numTrees[1]=1; (Empty tree? Valid. Single node tree? Also valid.)
• Build up the DP table:
  • For k = 2 to n:
  • For root = 1 to k:
    • Number of possible left subtrees: numTrees[root – 1]
    • Number of possible right subtrees: numTrees[k – root]
    • Add numTrees[root-1] * numTrees[k-root] to numTrees[k]
• Return numTrees[n]