Leetcode 95: Unique Binary Search Trees II

1. Problem Summary

You’re given an integer n. You need to generate all structurally unique Binary Search Trees (BSTs) that:

Have exactly n nodes.
Use all values from 1 to n exactly once (each value appears in exactly one node).
Follow BST property: left subtree < root < right subtree.

Input: n (1 ≤ n ≤ 8)

Output: A list of all different BST root nodes (trees), each representing a unique structure and node arrangement.

The order of the trees returned doesn’t matter.

2. Examples Explanation

Example 1:

Input: n = 3

Possible unique BST structures using values 1, 2, 3:

Root 1:

Right: BST formed from [2, 3] → options:

1 -> right = 2 -> right = 3 → [1,null,2,null,3]
1 -> right = 3, left child of 3 is 2 → [1,null,3,2]

Root 2:

Left: 1, Right: 3 → [2,1,3]

Root 3:

Left: BST formed from [1, 2] → options:

3 -> left = 1 -> right = 2 → [3,1,null,null,2]
3 -> left = 2, left child of 2 is 1 → [3,2,null,1]

Hence 5 unique trees.

Example 2:

Input: n = 1

Only one node with value 1, so only one BST: [1].

3. Approach

Pattern:

This is a recursive / divide-and-conquer tree construction problem based on the BST property.
Closely related to the Catalan-number counting problem (LeetCode 96), but here we must generate all structures.

Idea:

For any range of values [start, end], all unique BSTs formed from these values can be constructed by:

Choosing a root i where start <= i <= end.
Left subtree must be a BST made from values [start, i-1].
Right subtree must be a BST made from values [i+1, end].
Recursively generate all possibilities for left and right subtrees.
Combine each left subtree with each right subtree for root i.

The main function generateTrees(n) will call a helper like build(start, end) and return build(1, n).

Base Case:

If start > end: there is no number to put in this subtree ⇒ one “empty tree” possibility:

Return a list containing null, so that parent caller can attach null as a left or right child.

High-Level Steps:

Define build(start, end) that returns a list of TreeNode*/TreeNode representing all BSTs using values from start to end.
If start > end, return [null].
For each i in [start, end]:

Generate all left subtrees: leftTrees = build(start, i-1).
Generate all right subtrees: rightTrees = build(i+1, end).
For each combination (L in leftTrees, R in rightTrees):

Create a new root node root = new TreeNode(i).
Set root.left = L, root.right = R.
Add root to result list.

Return the result list.
Main function calls build(1, n).

Key Observations:

Number of unique BSTs is the Catalan number for n, but we’re generating all trees, not just counting.
Complexity is acceptable for n <= 8 (Catalan(8) = 1430 structures).
Using recursion with a list-return pattern is natural.
If desired, you can memoize build(start, end) to avoid recomputation, but for n <= 8 it’s not strictly necessary.

Pseudo-code:

Complexity Analysis:

Let Cn = n-th Catalan number (number of unique BSTs).

Time Complexity:

We generate each unique BST structure once and do O(n) work per tree (creating nodes / linking).
Roughly O(nCn) for n nodes.
For n <= 8, this is easily manageable.