95. Unique Binary Search Trees II - Explanation

1. Recursion

Intuition

To generate all unique BSTs with values from 1 to n, we pick each value as the root and recursively generate all possible left and right subtrees. When val is the root, values 1 to val-1 form the left subtree and values val+1 to n form the right subtree. We combine every leftTree with every rightTree to create all unique trees with that root.

Algorithm

Define a recursive function generate(left, right) that returns a list of all unique BSTs using values from left to right.
Base case: If left > right, return a list containing null (representing an empty subtree).
For each value val from left to right:
- Recursively generate all left subtrees using generate(left, val - 1).
- Recursively generate all right subtrees using generate(val + 1, right).
- For each combination of leftTree and rightTree, create a new tree with val as root and add it to res.
Return res.
Call generate(1, n) to get the final result.

# 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: int) -> List[Optional[TreeNode]]:
        def generate(left, right):
            if left > right:
                return [None]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)
            return res

        return generate(1, n)

Time & Space Complexity

Time complexity: $O(\frac {4 ^ n}{\sqrt {n}})$
Space complexity:
- $O(n)$ space for recursion stack.
- $O(\frac {4 ^ n}{\sqrt {n}})$ space for the output.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same ranges multiple times. For example, generate(2, 4) might be called from different parent recursions. We can cache results for each (left, right) pair to avoid regenerating the same subtrees.

Algorithm

Create a 2D memoization table dp to store results for each (left, right) pair.
Define a recursive function generate(left, right) similar to the basic recursive approach.
Before computing, check if dp[left][right] already has a value. If so, return the cached list.
Compute all trees for the range and store res in dp[left][right].
Return generate(1, n).

# 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: int) -> List[Optional[TreeNode]]:
        dp = {}

        def generate(left, right):
            if left > right:
                return [None]
            if (left, right) in dp:
                return dp[(left, right)]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)

            dp[(left, right)] = res
            return res

        return generate(1, n)

Time & Space Complexity

Time complexity: $O(\frac {4 ^ n}{\sqrt {n}})$
Space complexity:
- $O(n)$ space for recursion stack.
- $O(n ^ 2)$ extra space.
- $O(\frac {4 ^ n}{\sqrt {n}})$ space for the output.

3. Dynamic Programming (Bottom-Up)

Intuition

We can build the solution iteratively by computing all BSTs for smaller ranges first. We process ranges by increasing length: first all ranges of length 1, then length 2, and so on up to length n. This ensures that when we compute dp[left][right], all smaller subproblems are already solved.

Algorithm

Create a 2D table dp[left][right] to store all BSTs for each range.
Initialize base cases: For each i, set dp[i][i-1] = [null] (empty subtree).
For each length from 1 to n:
- For each starting position left where left + length - 1 <= n:
  - Let right = left + length - 1.
  - For each root value val from left to right:
    - Combine all trees from dp[left][val-1] and dp[val+1][right].
    - Create a new tree node for each combination and add to dp[left][right].
Return dp[1][n].

# 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: int) -> List[Optional[TreeNode]]:
        dp = [[[] for _ in range(n + 2)] for _ in range(n + 2)]
        for i in range(1, n + 2):
            dp[i][i - 1] = [None]

        for length in range(1, n + 1):
            for left in range(1, n - length + 2):
                right = left + length - 1
                dp[left][right] = []
                for val in range(left, right + 1):
                    for leftTree in dp[left][val - 1]:
                        for rightTree in dp[val + 1][right]:
                            root = TreeNode(val, leftTree, rightTree)
                            dp[left][right].append(root)

        return dp[1][n]

Time & Space Complexity

Time complexity: $O(\frac {4 ^ n}{\sqrt {n}})$
Space complexity:
- $O(n ^ 2)$ extra space.
- $O(\frac {4 ^ n}{\sqrt {n}})$ space for the output.

4. Dynamic Programming (Space Optimized)

Intuition

The number of unique BST structures depends only on the count of nodes, not their actual values. We can generate all BST structures for sizes 0, 1, 2, ..., n and then adjust node values using a shift function. For a tree structure with nodes 1 to k, we can create a tree with nodes offset+1 to offset+k by adding offset to each node's value.

Algorithm

Create an array dp[length] to store all BST structures for trees with length nodes.
Initialize dp[0] = [null] (empty tree).
For each length from 1 to n:
- For each root position val from 1 to length:
  - Left subtree has val - 1 nodes (from dp[val-1]).
  - Right subtree has length - val nodes (from dp[length-val]), but needs value shifting.
  - Create trees by combining leftTree from dp[val-1] with shift(rightTree, val) from dp[length-val].
Define a shift(node, offset) function that creates a new tree with all values increased by offset.
Return dp[n].

# 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: int) -> list[Optional[TreeNode]]:
        dp = [[] for _ in range(n + 1)]
        dp[0] = [None]

        for length in range(1, n + 1):
            dp[length] = []
            for val in range(1, length + 1):
                for leftTree in dp[val - 1]:
                    for rightTree in dp[length - val]:
                        root = TreeNode(val)
                        root.left = leftTree
                        root.right = self.shift(rightTree, val)
                        dp[length].append(root)

        return dp[n]

    def shift(self, node: Optional[TreeNode], offset: int) -> Optional[TreeNode]:
        if not node:
            return None
        root = TreeNode(node.val + offset)
        root.left = self.shift(node.left, offset)
        root.right = self.shift(node.right, offset)
        return root

Time & Space Complexity

Time complexity: $O(\frac {4 ^ n}{\sqrt {n}})$
Space complexity:
- $O(n)$ for the recursion stack.
- $O(n)$ extra space.
- $O(\frac {4 ^ n}{\sqrt {n}})$ space for the output.

Common Pitfalls

Returning Empty List Instead of List with Null

When the range is invalid (left > right), the base case should return a list containing null (representing an empty subtree), not an empty list. Returning an empty list causes the nested loops to skip all combinations, producing no trees at all.

Reusing Tree Nodes Across Different Trees

In the space-optimized approach, left subtrees are shared across multiple result trees since they have identical structure and values. However, right subtrees need to be cloned with shifted values. Forgetting to create new nodes when shifting values causes all trees to share and mutate the same nodes incorrectly.

Incorrect Value Shifting for Right Subtrees

When using the space-optimized DP approach, right subtree values must be shifted by the root value. A common mistake is applying the wrong offset or forgetting to recursively shift all nodes in the subtree. Each node in the right subtree should have offset added to its value.