# Leetcode: Unique Binary Search Trees II

Unique Binary Search Trees II

Similar Problems:

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

```For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```// Blog link: https://code.dennyzhang.com/unique-binary-search-trees-ii
// Basic Ideas: dynamic programming
// f(i):
//         j+1
//       /  \
//      /    \
//   f(j)    f(i-j-1)
// For the right subtree, add j+1 to the value of each node
//
// Complexity: Time O(2^n), Space O(2^n)
/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

func deepCopyWithAdd(root *TreeNode, v int) *TreeNode {
if root == nil { return nil }
res := &TreeNode{root.Val+v, nil, nil}
return res
}

func generateTrees(n int) []*TreeNode {
if n<=0 { return []*TreeNode{}}
l := [][]*TreeNode{}
l = append(l, []*TreeNode{nil})
l = append(l, []*TreeNode{&TreeNode{1, nil, nil}})
for i:=2; i<=n; i++ {
l2 := []*TreeNode{}
for j:=0; j<i; j++ {
for _, left := range l[j] {
for _, right := range l[i-j-1] {