# 95. Unique Binary Search Trees II

## Description

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]


Example 2:

Input: n = 1
Output: [[1]]


Constraints:

• 1 <= n <= 8

## Solutions

Solution 1: DFS (Depth-First Search)

We design a function $dfs(i, j)$ that returns all feasible binary search trees composed of $[i, j]$, so the answer is $dfs(1, n)$.

The execution steps of the function $dfs(i, j)$ are as follows:

1. If $i > j$, it means that there are no numbers to form a binary search tree at this time, so return a list consisting of a null node.
2. If $i \leq j$, we enumerate the numbers $v$ in $[i, j]$ as the root node. The left subtree of the root node $v$ is composed of $[i, v - 1]$, and the right subtree is composed of $[v + 1, j]$. Finally, we take the Cartesian product of all combinations of the left and right subtrees, i.e., $left \times right$, add the root node $v$, and get all binary search trees with $v$ as the root node.

The time complexity is $O(n \times G(n))$, and the space complexity is $O(n \times G(n))$. Where $G(n)$ is the Catalan number.

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
return dfs(1, n);
}

private List<TreeNode> dfs(int i, int j) {
List<TreeNode> ans = new ArrayList<>();
if (i > j) {
return ans;
}
for (int v = i; v <= j; ++v) {
var left = dfs(i, v - 1);
var right = dfs(v + 1, j);
for (var l : left) {
for (var r : right) {
}
}
}
return ans;
}
}

• /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
function<vector<TreeNode*>(int, int)> dfs = [&](int i, int j) {
if (i > j) {
return vector<TreeNode*>{nullptr};
}
vector<TreeNode*> ans;
for (int v = i; v <= j; ++v) {
auto left = dfs(i, v - 1);
auto right = dfs(v + 1, j);
for (auto l : left) {
for (auto r : right) {
ans.push_back(new TreeNode(v, l, r));
}
}
}
return ans;
};
return dfs(1, n);
}
};

• # Definition for a binary tree node.
# 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]:
def gen(left, right):
ans = []
# this if check instead of if left==right then return Node(left), less hassle
if left > right:
ans.append(None)
else:
# right+1, to cover case when left==right
for i in range(left, right + 1):
left_trees = gen(left, i - 1)
right_trees = gen(i + 1, right)
for l in left_trees:
for r in right_trees:
node = TreeNode(i, l, r)
ans.append(node)
return ans

return gen(1, n) # n or right is inclusive

############

# Definition for a binary tree node.
# 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[Optional[TreeNode]]:
def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
if i > j:
return [None]
ans = []
for v in range(i, j + 1):
left = dfs(i, v - 1)
right = dfs(v + 1, j)
for l in left:
for r in right:
ans.append(TreeNode(v, l, r))
return ans

return dfs(1, n)


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
var dfs func(int, int) []*TreeNode
dfs = func(i, j int) []*TreeNode {
if i > j {
return []*TreeNode{nil}
}
ans := []*TreeNode{}
for v := i; v <= j; v++ {
left := dfs(i, v-1)
right := dfs(v+1, j)
for _, l := range left {
for _, r := range right {
ans = append(ans, &TreeNode{v, l, r})
}
}
}
return ans
}
return dfs(1, n)
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function generateTrees(n: number): Array<TreeNode | null> {
const dfs = (i: number, j: number): Array<TreeNode | null> => {
if (i > j) {
return [null];
}
const ans: Array<TreeNode | null> = [];
for (let v = i; v <= j; ++v) {
const left = dfs(i, v - 1);
const right = dfs(v + 1, j);
for (const l of left) {
for (const r of right) {
ans.push(new TreeNode(v, l, r));
}
}
}
return ans;
};
return dfs(1, n);
}


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
Self::dfs(1, n)
}

fn dfs(i: i32, j: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
let mut ans = Vec::new();
if i > j {
ans.push(None);
return ans;
}
for v in i..=j {
let left = Self::dfs(i, v - 1);
let right = Self::dfs(v + 1, j);
for l in &left {
for r in &right {
ans.push(
Some(
Rc::new(
RefCell::new(TreeNode {
val: v,
left: l.clone(),
right: r.clone(),
})
)
)
);
}
}
}
ans
}
}