Domain 2MediumCORE

Unique Binary Search Trees II

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 $[1, dots, n]$. Constraints: Values are unique and ordered ($1$ through $n$). The constraint $N le 8$ 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 $1 dots i-1$ must form the left subtree and nodes $i+1 dots n$ must form the right subtree. This structural dependency is key to breaking down the problem recursively.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Tree

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 [1,…,n][1, \dots, n].
  • Constraints: Values are unique and ordered (11 through nn). The constraint N≤8N \le 8 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 1…i−11 \dots i-1 must form the left subtree and nodes i+1…ni+1 \dots n 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 (O(n!)O(n!)) and try to build a BST for each, then filter duplicates or invalid structures. That’s computationally infeasible even for N=8N=8.

Instead, we look at the properties of a BST:

  1. Root Selection: Any value from 11 to n can be the root.
  2. Subproblem Decomposition: Once a root is chosen (say value i), the problem splits into two independent subproblems: building all unique trees for values less than i and all unique trees for values greater than i.
  3. 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 1..n1..n, count is sufficient), memoizing results by range (start, end) prevents recomputing identical subtrees. Given constraints (N≤8N \le 8), 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].

  1. 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.
  2. Recursive Step: Iterate through every number i from start to end. Treat i as the root of a tree for this specific range.
  3. 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 value i, attach the specific left and right trees. Add this to our result list for range [start, end].
  4. Memoization: Store results of ranges in a cache (though strictly speaking not required for N=8N=8, it’s good practice).

Complexity Analysis

  • Time Complexity: The number of unique BSTs is given by the Catalan Number Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}. 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 O(Cn⋅n)O(C_n \cdot n) or simply dominated by output size generation.
  • Space Complexity: We need space for the recursion stack, which goes up to depth NN (O(N)O(N)). Additionally, we store the result list itself, which contains CnC_n trees with total nodes proportional to their count. Thus, auxiliary space (excluding output) is O(N)O(N) 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 N≥1N \ge 1, 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 only None and assigning it directly.
  • Single Node (n=1): The loop runs once for i=1, calls base cases which return [None], creates one tree, returns list with that single node.