The O(n) Club: Unique Binary Search Trees II: Recursion’s Party Trick

The O(n) Club: Unique Binary Search Trees II — Recursion’s Party Trick

⚡ TL;DR

Given n, build every possible BST using values 1 to n. Don’t brute-force every permutation—just pick each possible root, slap on all left/right subtree combos, and let recursion do the drudgery. Java style:

// Returns all unique BSTs storing values 1..n
public List
<treenode> generateTrees(int n) {
    if (n == 0) return new ArrayList<>();
    return buildTrees(1, n);
}</treenode>

🧠 How Devs Usually Mess This Up

The classic trap: obsessing over node orderings or busting out DP for a problem that can be solved with elegant recursion. Don’t sweep up value permutations or attempt to filter out duplicates later—that’s like mopping the rain. Instead, focus on tree structure. And unless n’s so big it needs its own zip code, forget the memoization. Save your DP flexing for another day.

🔍 What’s Actually Going On

Here’s the deal: For every number i in 1 to n, make i the root. What goes left? Everything smaller. What goes right? Everything larger. Recursively do this for every subtree. Every possible left subtree gets matched with every possible right subtree, all grafted to root i. Think of it as mixing and matching Lego limbs until you run out of permutations—but only legal ones that actually look like real trees!

🛠️ PseudoCode

• Base Case: If start > end, return [null] (empty tree, not a Java NullPointer party).
• Loop: For every i in (start..end):
  • Recursively generate all left trees for (start, i-1)
  • Recursively generate all right trees for (i+1, end)
  • For every left/right pair, attach them to new root i
  • Add the happy new tree to your result list
• Return the result list (ta-da: all trees for this range!)

// Java-style pseudocode
List
<treenode> buildTrees(int start, int end) {
    if (start > end) return [null];
    List
<treenode> trees = [];
    for (int i = start; i <= end; i++) {
        leftList = buildTrees(start, i-1);
        rightList = buildTrees(i+1, end);
        for (TreeNode left : leftList)
            for (TreeNode right : rightList)
                trees.add(new TreeNode(i, left, right));
    }
    return trees;
}
</treenode></treenode>

💻 The Code

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
    TreeNode(int x, TreeNode l, TreeNode r) {
        val = x; left = l; right = r;
    }
}
 public List
<treenode> generateTrees(int n) {
    if (n == 0) return new ArrayList<>();
    return buildTrees(1, n);
}
 private List
<treenode> buildTrees(int start, int end) {
    List
<treenode> result = new ArrayList<>();
    if (start > end) {
        result.add(null);
        return result;
    }
    for (int i = start; i <= end; i++) {
        List
<treenode> leftTrees = buildTrees(start, i - 1);
        List
<treenode> rightTrees = buildTrees(i + 1, end);
        for (TreeNode l : leftTrees) {
            for (TreeNode r : rightTrees) {
                result.add(new TreeNode(i, l, r));
            }
        }
    }
    return result;
}
</treenode></treenode></treenode></treenode></treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• n == 0? Just return an empty list and resist the urge to crash.
• Structure rules! Generating stuff out of order? You’ll get clones. Don’t filter for structure at the end—you’ll go cross-eyed.
• Time/Space: It’s roughly O(3^n). Great for n < 9. Any more, and your CPU starts writing haikus about recursion.
• Null branches are valid children, not mistakes. Embrace the stumpy trees!

🧠 Interviewer Brain-Tattoo

“When in doubt, put recursion in charge. If that’s not enough, you’re probably being trolled by the problem setter.”