95. Unique Binary Search Trees II
Given an integer n, build every structurally distinct binary search tree that stores exactly the values 1 through n, and return a list of their root nodes (each node has an integer value and left/right children). Two trees count as different when their shapes differ anywhere — the BST ordering rule (left subtree smaller, right subtree larger) is what pins which values can go where.
For n = 3 there are exactly five such trees (see the figure).
You may return the roots in any order: the judge serializes each tree in preorder with # marking a missing child and prints the serializations in lexicographic order, so any correct set of trees produces the same output. Subtrees may be shared between returned trees — they are only read, never modified.
Example 1:
Input: n = 3
Output: 5 trees, e.g. the balanced one serializes as "2 1 # # 3 # #"
Explanation: Five shapes exist for the values {1, 2, 3}: two right chains rooted at 1, the balanced tree rooted at 2, and two left-leaning shapes rooted at 3.
Example 2:
Input: n = 1
Output: 1 tree: the lone node 1
Explanation: A single node is the only BST holding just the value 1.
Constraints:
- 1 ≤ n ≤ 8
- The number of trees is the n-th Catalan number: 1, 2, 5, 14, 42, 132, 429, 1430.
Hints:
Pick the root first. If value i is the root, the values 1..i−1 must form its left subtree and i+1..n its right subtree — both are themselves BST-building problems on a smaller range.
Write build(lo, hi) returning every BST over the values lo..hi. Combine: for each root i and each (leftTree, rightTree) pair from build(lo, i−1) × build(i+1, hi), make a node. The empty range must return [None] — a list containing 'no tree' — or the cross product collapses to nothing.
The same (lo, hi) range is rebuilt many times across different roots. Memoize the range → list-of-trees mapping; shared subtrees are safe because the trees are never mutated afterward.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: 5 trees — preorder lines: "1 # 2 # 3 # #", "1 # 3 2 # # #", "2 1 # # 3 # #", "3 1 # 2 # # #", "3 2 1 # # # #"