**Solution**

**Unique Binary Search Trees II** https://leetcode.com/problems/unique-binary-search-trees-ii/

Dynamic Programming Approach

- The number of different roots can range from 1 to i
- We do not need to change left subtree. But right subtree vals has to be shifted.
- Take i = 10 and j = 6. Left subtree [1,5] and right subtree [7-10].
- Right subtree has 4 nodes and all the trees in it will be structurally similar to trees with [1-4] nodes.
- So we simply need to copy each tree for [1-4] and shift its value by offset.
- Copy tree will use a tree traversal like pre-order.
- In this problem even if we use dp, we should copy the cached result each time we use it instead of the cached result itself. So we won't actually save time.

Recursive Approach:

- In this problem even if we use dp, we should copy the cached result each time we use it instead of the cached result itself. So we won't actually save time.

```
class Solution(object):
def helper(self, start, end):
result = []
if start > end:
result.append(None)
else:
for root in range(start, end+1):
left, right = self.helper(start, root-1), self.helper(root+1, end)
for lt in left:
for rt in right:
x = TreeNode(root)
x.left, x.right = lt, rt
result.append(x)
return result
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.helper(1, n)
```