# Unique Binary Search Trees II LeetCode Solution

Here, We see Unique Binary Search Trees II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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

## Unique Binary Search Trees II Leetcode Solution C++

``````class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if(n == 0)	return vector<TreeNode *>(1, NULL);
vector<vector<vector<TreeNode*>>> subtree(n+2, vector<vector<TreeNode*>>(n+2, vector<TreeNode*>()));
for(int i=1; i<=n+1; ++i){
subtree[i][i].push_back(new TreeNode(i));
subtree[i][i-1].push_back(NULL);
}
for(int l=2; l<=n; ++l){
for(int i=1; i<=n-l+1; ++i){
for(int j=i; j<=i+l-1; ++j){
for(int k=0; k<subtree[j+1][i+l-1].size(); ++k){
for(int m=0; m<subtree[i][j-1].size(); ++m){
TreeNode *T = new TreeNode(j);
T->left = subtree[i][j-1][m];
T->right = subtree[j+1][i+l-1][k];
subtree[i][i+l-1].push_back(T);
}
}
}
}
}
return subtree[1][n];
}
};```Code language: PHP (php)```

## Unique Binary Search Trees II Leetcode Solution Java

``````class Solution {
public List<TreeNode> generateTrees(int n) {
return generateTrees(1,n);
}

public List<TreeNode> generateTrees(int start,int end){
List<TreeNode> trees = new ArrayList<TreeNode>();
if(start>end){  trees.add(null); return trees;}

for(int rootValue=start;rootValue<=end;rootValue++){
List<TreeNode> leftSubTrees=generateTrees(start,rootValue-1);
List<TreeNode> rightSubTrees=generateTrees(rootValue+1,end);

for(TreeNode leftSubTree:leftSubTrees){
for(TreeNode rightSubTree:rightSubTrees){
TreeNode root=new TreeNode(rootValue);
root.left=leftSubTree;
root.right=rightSubTree;
trees.add(root);
}
}
}
return trees;
}
}```Code language: PHP (php)```

## Unique Binary Search Trees II Leetcode Solution JavaScript

``````var generateTrees = function(n) {
const constructArray = (start, end) => {
const result = [];

if(start > end){
return [null];
}

if(start===end){
return [new TreeNode(start)];
}

if(end-start===1){
const first = new TreeNode(start, null, new TreeNode(end));
const second = new TreeNode(end, new TreeNode(start), null);
return [first, second];
}

for(let i=start; i<=end; i++){
const leftSide = constructArray(start, i-1);
const rightSide = constructArray(i+1, end);

leftSide.forEach(ls => {
rightSide.forEach(rs => {
const tree = new TreeNode(i, ls, rs);

result.push(tree);
})
})
}
return result;
}
return constructArray(1,n);
};```Code language: JavaScript (javascript)```

## Unique Binary Search Trees II Leetcode Solution Python

``````class Solution(object):
def generateTrees(self, n):
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, left, right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)] or [None]
return trees(1, n)``````
Scroll to Top