Pattern visualizer

Unique Binary Search Trees II

Unlike counting unique BSTs, here every tree itself has to be built. For a range [start, end], try every value i as the root: everything in [start, i-1] can be any valid left subtree, everything in [i+1, end] can be any valid right subtree, and every LEFT/RIGHT pairing is a distinct valid tree. The base case must return a list holding one null (not an empty list), or the combine loops below never run and no trees get built at all. Animated on: n = 3 — generate all structurally unique BSTs whose nodes hold values 1..3, and return their root nodes. Expected: 5 trees (the 3rd Catalan number)..

Pick every possible root, then cartesian-combine its left and right subtree lists

time O(4^n / n^(1/2))space O(4^n / n^(1/2))step 1 / 10

Call stack

generate(1, 3)generate(2, 3)generate(3, 3)

line 4

Range [3, 3] with only value 3 left in it: both generate(3, 2) and generate(4, 3) hit start > end and return a list holding one null, not an empty list. An empty list would make the combine loops below run zero times and produce no trees at all. Combining null with null under 3 gives the first real node: 3 (a leaf).

Pseudocode

1FUNCTION generateTrees(n):
2  RETURN generate(1, n)
3FUNCTION generate(start, end):
4  IF start > end: RETURN [null]
5  trees <- []
6  FOR i <- start TO end:
7    leftTrees <- generate(start, i - 1)
8    rightTrees <- generate(i + 1, end)
9    FOR EACH l IN leftTrees:
10      FOR EACH r IN rightTrees:
11        root <- NEW NODE(i, l, r)
12        APPEND root TO trees
13  RETURN trees

← / → step · space play · Home restart

Where to practice BST

Practice BST problems All BST problems Back to roadmap