# 95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

# Solution

Approach 1: Recursion with brute force. Make sure to generate a new tree each time so that the trees don't get modified.

Approach 2: DP based on n with value offset.

# Code (Python)

Approach 1:

class Solution:
    def generateTrees(self, n: 'int') -> 'List[TreeNode]':
        if n == 0:
            return []
        return self._generate(1, n)
    
    def _generate(self, lo, hi):
        if lo > hi:
            return [None]
        if lo == hi:
            return [TreeNode(lo)]
        result = []
        for root_val in range(lo, hi + 1):
            for left_tree in self._generate(lo, root_val - 1):
                for right_tree in self._generate(root_val + 1, hi):
                    root = TreeNode(root_val)
                    root.left = left_tree
                    root.right = right_tree
                    result.append(root)
        return result

Approach 2:

# Code (C++)

Approach 1:

// Recursion.
class Solution {
private:
    vector<TreeNode*> doGenerateTrees(int head, int tail) {
        vector<TreeNode*> trees;
        if (head > tail)
        {
            trees.push_back(NULL);
        }
        for (int i = head; i <= tail; ++i)
        {
            vector<TreeNode*> leftSet = doGenerateTrees(head, i - 1);
            vector<TreeNode*> rightSet = doGenerateTrees(i + 1, tail);
            for (int j = 0; j < leftSet.size(); ++j)
            {
                for (int k = 0; k < rightSet.size(); ++k)
                {
                    TreeNode *node = new TreeNode(i);
                    node->left = leftSet[j];
                    node->right = rightSet[k];
                    trees.push_back(node);
                }
            }
        }
        return trees;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0)
            return vector<TreeNode*>();
        return doGenerateTrees(1, n);
    }
};

Approach 2:

// DP based on n with value offset.
class Solution {
private:
    // Trees with the same size are structurally the same.
    // Just need to add the offset for each nodes's value.
    TreeNode* cloneTree(TreeNode *root, int offset) {
        if (root == NULL)
            return NULL;
        TreeNode *node = new TreeNode(root->val + offset);
        node->left = cloneTree(root->left, offset);
        node->right = cloneTree(root->right, offset);
        return node;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0)
            return vector<TreeNode*>();
        vector<TreeNode*> treeMap[n+1];
        treeMap[0].push_back(NULL);
        for (int len = 1; len <= n; ++len)
        {
            for (int root = 1; root <= len; ++root)
            {
                int leftLen = root - 1;
                int rightLen = len - root;
                for (int leftRoot = 0; leftRoot < treeMap[leftLen].size(); ++leftRoot)
                {
                    for (int rightRoot = 0; rightRoot < treeMap[rightLen].size(); ++rightRoot)
                    {
                        TreeNode *node = new TreeNode(root);
                        node->left = cloneTree(treeMap[leftLen][leftRoot], 0);
                        node->right = cloneTree(treeMap[rightLen][rightRoot], root);
                        treeMap[len].push_back(node);
                    }
                }
            }
        }
        return treeMap[n];
    }
};