DSA Tracker

Visualize

Unique Binary Search Trees II

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))

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.

Details

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).

Problem:Unique Binary Search Trees IIMedium

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

step 1 / 10

3

Call stack

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

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

Every step in words

Show all 10 steps
  1. 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).
  2. Back in generate(2, 3): root 2, left range is empty (null) and the right range [3, 3] already resolved to the leaf just built. Attach it as 2's right child.
  3. Same trivial pattern one level down: range [2, 2] has only value 2, so it builds a lone leaf 2 (a leaf).
  4. Root 3 for range [2, 3]: left range [2, 2] resolved to the leaf just built, right range is empty. This is a DIFFERENT shape from the previous tree — same two values, mirrored. generate(2, 3) is now done: it returns both of these 2 shapes.
  5. Top call generate(1, 3), root 1: left range is empty, right range [2, 3] just returned 2 shapes. Combine null with the first one, 2 (left=null, right=3), under root 1: the first complete answer.
  6. Same root 1, second right shape: 3 (left=2, right=null). Combining it gives a second, structurally different tree. Root 1 alone has now contributed 2 trees to the answer, one per shape generate(2, 3) returned.
  7. Root 2: ranges [1, 1] and [3, 3] are each a single value, so both sides trivially built one-node trees. Combine them as 2's left and right child — root 2 contributes exactly 1 tree, since both sides only ever had 1 shape.
  8. Root 3: right range [4, 3] is empty. Left range [1, 2] hit the exact same 2-shape pattern as [2, 3] did earlier, just shifted down by one value. Take its first shape, 1 (left=null, right=2), as 3's left child.
  9. And its second shape, 2 (left=1, right=null), as 3's left child gives the fifth and final tree.
  10. generate(1, 3) is done: 5 structurally unique trees were produced — one for each choice of root under the divide-and-combine rule. This matches the 3rd Catalan number, C(3) = 5, which counts exactly this: the number of distinct binary tree shapes on 3 nodes.

Now solve it yourself

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

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