# Unique Binary Search Trees II    ## Intuition

This is a typical DP problem which could be solved recursivly.

Let's start from the defination of binary search tree. For each node, the nodes on its left sub-tree is always less than itself. And nodes on its right sub-tree is always greater than itself.

So, by choosing a root value from n nodes, the numbers would be grouped into 2 sets. Smaller set is all on its left and bigger set is all on its right. That how this solution comes from.

## Solution

``````
#
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def generateTrees(self, n):
if n <= 0:
return []
self.cache = {}
return self._dfs(0, n + 1)

def _dfs(self, lo, hi):
if hi - lo == 1:
return [None]
if (lo, hi) not in self.cache:
ans = []
for mid in range(lo + 1, hi):
for left in self._dfs(lo, mid):
for right in self._dfs(mid, hi):
current = TreeNode(mid)
current.left = left
current.right = right
ans.append(current)
self.cache[(lo, hi)] = ans
return self.cache[(lo, hi)]

``````