Given an integer n, you are asked to generate all structurally unique Binary Search Trees (BSTs) that store values 1 through n. Each tree must use each number from 1 to n exactly once, and the structure of the BSTs must be unique (no duplicate tree shapes, even if the values are arranged differently).
The function signature is typically:
List<TreeNode> generateTrees(int n)
n once and only once.n == 0.
The problem asks us to generate all unique BSTs for a given number n, not just count them. A brute-force approach would try every possible combination of left and right subtrees for every root, but this quickly becomes infeasible as n grows because the number of trees grows exponentially.
The key insight is recognizing that for each possible root value, the numbers less than the root form the left subtree, and the numbers greater form the right subtree. By recursively generating all left and right subtrees for each root, and combining them, we can build all unique BSTs.
This is a classic recursive problem, and with memoization, we can avoid recomputing subproblems. However, since we need to generate all trees (not just count), memoization is less effective, but recursion is still the best fit.
We'll use recursion to build all possible trees:
[start, end], we consider each number i in that range as the root.
i, recursively generate all possible left subtrees from [start, i-1] and all possible right subtrees from [i+1, end].
start > end, return a list containing None (representing an empty tree).
This approach ensures that all unique structures are generated. The recursive combination of left and right subtrees for each root guarantees that no structure is missed or duplicated.
Let's walk through the process for n = 3:
For [2,3], root can be 2 (with 3 on the right) or 3 (with 2 on the left).
Both are single-node trees.
For [1,2], root can be 1 (with 2 on the right) or 2 (with 1 on the left).
By combining all these, we get 5 unique BSTs for n = 3.
Brute-force: The number of structurally unique BSTs for n nodes is the Catalan number C_n, which grows exponentially as O(4^n / n^{3/2}). Brute-force would try all possible combinations, which is extremely slow and inefficient.
Optimized Recursive Approach:
C_n unique BSTs, and for each, we construct a tree, so time is at least O(C_n).
O(n) space at most.
Note: If only counting the number, dynamic programming can reduce time to O(n^2), but to generate all trees, we must enumerate them.
This problem elegantly demonstrates recursive tree construction. By considering each value as the root and recursively building all left and right subtrees, we can generate all unique BSTs for values 1 to n. The approach is simple, yet powerful, and highlights the beauty of recursive problem-solving for tree structures.
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def generateTrees(self, n):
if n == 0:
return []
def build(start, end):
trees = []
if start > end:
return [None]
for i in range(start, end + 1):
left_trees = build(start, i - 1)
right_trees = build(i + 1, end)
for l in left_trees:
for r in right_trees:
root = TreeNode(i)
root.left = l
root.right = r
trees.append(root)
return trees
return build(1, n)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return {};
return build(1, n);
}
vector<TreeNode*> build(int start, int end) {
vector<TreeNode*> trees;
if (start > end) {
trees.push_back(nullptr);
return trees;
}
for (int i = start; i <= end; ++i) {
vector<TreeNode*> left = build(start, i - 1);
vector<TreeNode*> right = build(i + 1, end);
for (TreeNode* l : left) {
for (TreeNode* r : right) {
TreeNode* root = new TreeNode(i);
root->left = l;
root->right = r;
trees.push_back(root);
}
}
}
return trees;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new ArrayList<>();
return build(1, n);
}
private List<TreeNode> build(int start, int end) {
List<TreeNode> trees = new ArrayList<>();
if (start > end) {
trees.add(null);
return trees;
}
for (int i = start; i <= end; i++) {
List<TreeNode> left = build(start, i - 1);
List<TreeNode> right = build(i + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
trees.add(root);
}
}
}
return trees;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
if (n === 0) return [];
function build(start, end) {
let trees = [];
if (start > end) {
trees.push(null);
return trees;
}
for (let i = start; i <= end; i++) {
let left = build(start, i - 1);
let right = build(i + 1, end);
for (let l of left) {
for (let r of right) {
let root = new TreeNode(i);
root.left = l;
root.right = r;
trees.push(root);
}
}
}
return trees;
}
return build(1, n);
};