95. Unique Binary Search Trees II
Model: qwen3.5:9b
Topics: Dynamic Programming,Tree
FAANG asked: 1
Acceptance rate: 43.0%
Problem Breakdown
We are asked to construct all structurally unique Binary Search Trees (BSTs) that contain exactly n nodes with values from 1 to n.
- Input: An integer
n. - Output: A list of tree roots, where each root represents a complete BST containing the integers .
- Constraints: Values are unique and ordered ( through ). The constraint is small enough that we don’t need to worry about memory limits for storing all trees, but it does imply an exponential output size (Catalan numbers), so efficiency matters.
- Implicit Logic: In a BST, the root determines which values go left and right. If
root = i, then nodes must form the left subtree and nodes must form the right subtree. This structural dependency is key to breaking down the problem recursively.
Intuition
A brute-force approach would be to generate all permutations of numbers from 1 to n () and try to build a BST for each, then filter duplicates or invalid structures. That’s computationally infeasible even for .
Instead, we look at the properties of a BST:
- Root Selection: Any value from to
ncan be the root. - Subproblem Decomposition: Once a root is chosen (say value
i), the problem splits into two independent subproblems: building all unique trees for values less thaniand all unique trees for values greater thani. - Combination: For every valid left subtree configuration, we can combine it with every valid right subtree configuration to form a complete tree rooted at
i.
This suggests recursion or Dynamic Programming (DP). Since the subproblems depend on ranges of numbers rather than just counts (though for this specific problem , count is sufficient), memoizing results by range (start, end) prevents recomputing identical subtrees. Given constraints (), pure recursion works, but a DP approach demonstrates better engineering habits for larger inputs.
Approach
I will implement a recursive helper function generate(start, end). This function returns a list of all unique BSTs that can be formed using values in the range [start, end].
- Base Case: If
start > end, it means we have an empty tree (null). We return a list containing one element:None(representing an empty node), so that when combining with children later, we can handle null pointers correctly in the loop logic. - Recursive Step: Iterate through every number
ifromstarttoend. Treatias the root of a tree for this specific range. - Combine Subtrees:
- Get all left subtrees:
generate(start, i-1) - Get all right subtrees:
generate(i+1, end) - Iterate through every combination
(left_tree, right_tree). Create a new root node with valuei, attach the specific left and right trees. Add this to our result list for range[start, end].
- Get all left subtrees:
- Memoization: Store results of ranges in a cache (though strictly speaking not required for , it’s good practice).
Complexity Analysis
- Time Complexity: The number of unique BSTs is given by the Catalan Number . For each tree, we perform constant work to link nodes. However, since we construct every node in every possible tree exactly once across all recursive calls (excluding overhead), it’s roughly proportional to the total number of nodes generated across all trees. The complexity is or simply dominated by output size generation.
- Space Complexity: We need space for the recursion stack, which goes up to depth (). Additionally, we store the result list itself, which contains trees with total nodes proportional to their count. Thus, auxiliary space (excluding output) is due to call stack and cache map size.
Solution
# 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
from typing import List, Optional
def generateTrees(n: int) -> List[Optional['TreeNode']]:
if n == 0:
return []
# Cache to store results for specific ranges [start, end]
memo = {}
def build_trees(start: int, end: int) -> List[Optional['TreeNode']]:
# Base case: empty range represents a null tree (empty list containing None is tricky in Python lists logic usually we return [None])
if start > end:
return [None]
key = f"{start}-{end}"
if key not in memo:
result_list = []
# Try every number as the root for this range
for i in range(start, end + 1):
left_trees = build_trees(start, i - 1)
right_trees = build_trees(i + 1, end)
# Cartesian product of left and right subtrees
for l_tree in left_trees:
for r_tree in right_trees:
root = TreeNode(val=i)
root.left = l_tree
root.right = r_tree
result_list.append(root)
memo[key] = result_list
return memo.get(key, [])
# Start recursion with range 1 to n
return build_trees(1, n)
Edge Cases Handled
n=0: The function returns an empty list immediately. (Though constraints say , this is robust).- Empty Subtrees: When
start > end, the helper returns[None]. This allows a root node to have no left child or no right child naturally by iterating over lists containing onlyNoneand assigning it directly. - Single Node (
n=1): The loop runs once fori=1, calls base cases which return[None], creates one tree, returns list with that single node.