# Unique Binary Search Trees II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unique-binary-search-trees-ii)
Canonical: https://scaleengineer.com/dsa/problems/unique-binary-search-trees-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Uber](https://scaleengineer.com/companies/uber)
---
## Problem
Given an integer `n`, return _all the structurally unique **BST'**s (binary search trees), which has exactly_ `n` _nodes of unique values from_ `1` _to_ `n`. Return the answer in **any order**.

**Example 1:**

![](https://assets.glich.co/dsa/unique-binary-search-trees-ii/image0.jpg) 

**Input:** n = 3
**Output:** [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

**Example 2:**

**Input:** n = 1
**Output:** [[1]]

**Constraints:**

* `1 <= n <= 8`

# Approaches
## Brute-force Recursion
This approach uses a straightforward recursive method to construct all possible Binary Search Trees. The core idea is based on the definition of a BST: for any chosen root `i` from the range `[1, n]`, all values smaller than `i` must go into the left subtree, and all values larger than `i` must go into the right subtree. We can recursively generate all possible left and right subtrees and then combine them for each choice of root `i`.
**Time:** Exponential, O(3^N) · **Space:** O(N * G_N)
**Pros:** The logic is simple and directly follows the mathematical definition of constructing BSTs.; It's relatively easy to implement.
**Cons:** Highly inefficient due to massive re-computation of the same subproblems. For example, generating trees for a range of a certain length is done multiple times with different value offsets.
### Explanation
The algorithm defines a helper function, `generateSubtrees(start, end)`, which is responsible for generating all BSTs using numbers from `start` to `end`. For each number `i` in this range, we consider it as the root. Then, we recursively call the function to generate all possible left subtrees from the range `[start, i-1]` and all possible right subtrees from `[i+1, end]`. Finally, we combine each left subtree with each right subtree to form a new tree rooted at `i`.

The base case for the recursion is when `start > end`, which represents an empty range. In this case, we return a list containing `null` to signify an empty subtree. This `null` is crucial for the loops that combine subtrees, ensuring they execute correctly even when one side is empty.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateSubtrees(1, n);
    }

    private List<TreeNode> generateSubtrees(int start, int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        // Pick each number in the range as a root
        for (int i = start; i <= end; i++) {
            // Generate all possible left subtrees
            List<TreeNode> leftSubtrees = generateSubtrees(start, i - 1);
            // Generate all possible right subtrees
            List<TreeNode> rightSubtrees = generateSubtrees(i + 1, end);

            // Combine each left subtree with each right subtree
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTrees.add(root);
                }
            }
        }
        return allTrees;
    }
}
```
### Algorithm
1. Define a recursive function, say `generate(start, end)`, that returns a list of all unique BSTs for values in the range `[start, end]`.
2. The main function calls `generate(1, n)`.
3. In `generate(start, end)`:
   - If `start > end`, it signifies an empty subtree. Return a list containing a single `null` element to represent this.
   - Initialize an empty list, `all_trees`, to store the generated BSTs for the current range.
   - Iterate with a loop variable `i` from `start` to `end`. This `i` will serve as the root of a BST.
   - Make a recursive call to `generate(start, i-1)` to get all possible left subtrees.
   - Make another recursive call to `generate(i+1, end)` to get all possible right subtrees.
   - Nest two loops to iterate through each `left_tree` from the list of left subtrees and each `right_tree` from the list of right subtrees.
   - Inside the loops, for each pair of `(left_tree, right_tree)`, create a new `TreeNode` with value `i`. Set its `left` child to `left_tree` and its `right` child to `right_tree`.
   - Add this newly constructed tree to the `all_trees` list.
4. After the loops complete, return the `all_trees` list.

## Dynamic Programming with Memoization
This approach optimizes the brute-force recursive solution by using dynamic programming with memoization. The plain recursive solution suffers from re-calculating the results for the same subproblems (i.e., same ranges of numbers) multiple times. By storing the list of generated trees for each range `[start, end]` in a cache, we can avoid these redundant computations. When the function is called for a range that has been solved before, we can simply retrieve the result from the cache in constant time.
**Time:** O(N * G_N) · **Space:** O(N * G_N)
**Pros:** Significantly more efficient than the brute-force approach by eliminating redundant computations.; Guarantees that each subproblem is solved only once.
**Cons:** Requires additional space for the memoization table, which can be significant.
### Explanation
The core of this approach is a memoization table, `memo`, which is typically a 2D array. `memo[start][end]` will store the list of all unique BSTs that can be formed from the numbers in the range `[start, end]`. 

The recursive helper function is modified to accept this memoization table. Before any computation, it checks if the result for the current `(start, end)` pair is already in the table. If so, it returns the cached value. Otherwise, it computes the result just like the brute-force method. Once the list of trees for the current range is generated, it's stored in `memo[start][end]` before being returned. This ensures that each subproblem is solved only once.

This technique transforms the exponential time complexity of the naive recursion into a more manageable one, making it efficient enough for the given constraints.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        List<TreeNode>[][] memo = new List[n + 1][n + 1];
        return generateSubtrees(1, n, memo);
    }

    private List<TreeNode> generateSubtrees(int start, int end, List<TreeNode>[][] memo) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        if (memo[start][end] != null) {
            return memo[start][end];
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftSubtrees = generateSubtrees(start, i - 1, memo);
            List<TreeNode> rightSubtrees = generateSubtrees(i + 1, end, memo);

            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTrees.add(root);
                }
            }
        }
        
        memo[start][end] = allTrees;
        return allTrees;
    }
}
```
### Algorithm
1. Create a cache, for instance, a 2D array `memo[n+1][n+1]`, to store the lists of `TreeNode`s for previously computed ranges.
2. Define a recursive helper function `generate(start, end, memo)`.
3. In `generate(start, end, memo)`:
   - If `start > end`, return a list containing `null`.
   - Check if `memo[start][end]` contains a result. If it does, return the cached list immediately.
   - If the result is not in the cache, proceed with the same logic as the brute-force approach:
     - Initialize an empty list `all_trees`.
     - Loop `i` from `start` to `end` to select a root.
     - Recursively call `generate(start, i-1, memo)` for left subtrees.
     - Recursively call `generate(i+1, end, memo)` for right subtrees.
     - Combine each left and right subtree pair to form new trees with root `i` and add them to `all_trees`.
   - Before returning, store the computed `all_trees` list in `memo[start][end]` to cache the result.
4. The main function initializes the cache and calls `generate(1, n, memo)`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < TreeNode > generateTrees ( int n ) { return dfs ( 1 , n ); } private List < TreeNode > dfs ( int i , int j ) { List < TreeNode > ans = new ArrayList <>(); if ( i > j ) { ans . add ( null ); return ans ; } for ( int v = i ; v <= j ; ++ v ) { var left = dfs ( i , v - 1 ); var right = dfs ( v + 1 , j ); for ( var l : left ) { for ( var r : right ) { ans . add ( new TreeNode ( v , l , r )); } } } return ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < TreeNode *> generateTrees ( int n ) { function < vector < TreeNode *> ( int , int ) > dfs = [ & ]( int i , int j ) { if ( i > j ) { return vector < TreeNode *> { nullptr }; } vector < TreeNode *> ans ; for ( int v = i ; v <= j ; ++ v ) { auto left = dfs ( i , v - 1 ); auto right = dfs ( v + 1 , j ); for ( auto l : left ) { for ( auto r : right ) { ans . push_back ( new TreeNode ( v , l , r )); } } } return ans ; }; return dfs ( 1 , n ); } };
```

### Python

```python
# 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 [ TreeNode ]: def gen ( left , right ): ans = [] # this if check instead of if left==right then return Node(left), less hassle if left > right : ans . append ( None ) else : # right+1, to cover case when left==right for i in range ( left , right + 1 ): left_trees = gen ( left , i - 1 ) right_trees = gen ( i + 1 , right ) for l in left_trees : for r in right_trees : node = TreeNode ( i , l , r ) ans . append ( node ) return ans return gen ( 1 , n ) # n or right is inclusive ############ # 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 dfs ( i : int , j : int ) -> List [ Optional [ TreeNode ]]: if i > j : return [ None ] ans = [] for v in range ( i , j + 1 ): left = dfs ( i , v - 1 ) right = dfs ( v + 1 , j ) for l in left : for r in right : ans . append ( TreeNode ( v , l , r )) return ans return dfs ( 1 , n )
```