## Similar Problems

Similar Problems not available

# Unique Binary Search Trees Ii - Leetcode Solution

LeetCode: Unique Binary Search Trees Ii Leetcode Solution

Difficulty: Medium

Topics: binary-search-tree dynamic-programming tree binary-tree backtracking

Problem statement

Given an integer `n`

, generate all structurally unique binary search trees that store values `1`

to `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]
]
```

Each tree is represented as a list of `TreeNode`

objects, where the `val`

attribute represents the integer value stored in the node, and the `left`

and `right`

attributes represent the left and right subtrees, respectively. A `null`

value represents an empty subtree.

Solution

The problem can be solved using recursive methods. For each value `val`

from `1`

to `n`

, we can create the root of a binary search tree with that value, and then recursively generate all possible left and right subtrees for that root. We can then combine each possible left and right subtree with the root to generate all possible binary search trees.

To optimize the algorithm, we can use memoization to store the results of previous recursive calls. This will avoid recomputing the same results multiple times.

We can implement the solution using the following steps:

- Define a recursive function
`generateTrees(start, end)`

that generates all structurally unique binary search trees using the range of integer values from`start`

to`end`

. - Base case: If
`start > end`

, return a list with a single`None`

element. - Loop through the integer values from
`start`

to`end`

, and for each value`val`

, do the following:- Recursively generate all possible left subtrees with integer values from
`start`

to`val - 1`

, and store the result in a variable`left`

. - Recursively generate all possible right subtrees with integer values from
`val + 1`

to`end`

, and store the result in a variable`right`

. - Loop through each possible left subtree in
`left`

, and for each left subtree, loop through each possible right subtree in`right`

, and combine them with the root node`val`

to generate a new binary search tree. - Append the list of generated binary search trees to a variable
`trees`

.

- Recursively generate all possible left subtrees with integer values from
- Return the list of generated binary search trees in
`trees`

.

Using memoization, we can store the results of previous recursive calls in a dictionary `memo`

, where the key is a tuple `(start, end)`

representing the range of integer values, and the value is the list of generated binary search trees.

The final implementation in Python is given below:

```
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]:
if n == 0:
return []
memo = {}
def generateTreesHelper(start, end):
if start > end:
return [None]
if (start, end) in memo:
return memo[(start, end)]
trees = []
for val in range(start, end+1):
left = generateTreesHelper(start, val-1)
right = generateTreesHelper(val+1, end)
for leftSubtree in left:
for rightSubtree in right:
root = TreeNode(val)
root.left = leftSubtree
root.right = rightSubtree
trees.append(root)
memo[(start, end)] = trees
return trees
return generateTreesHelper(1, n)
```

Time Complexity

There are `n`

nodes in each tree, and for each node, we need to generate all possible left and right subtrees. Therefore, the time complexity of the algorithm is `O(n * Cn)`

, where `Cn`

is the nth Catalan number, which is the number of unique binary search trees that can be formed with `n`

nodes. The recursive function `generateTreesHelper`

is called for each possible range of integer values from `1`

to `n`

, and since there are `n`

possible ranges, the space complexity of the algorithm is `O(n * Cn)`

.

## Unique Binary Search Trees Ii Solution Code

`1`