### Generate all Possible Unique Binary Search Trees - The Coding Shala

Last Updated: 27-Jan-2021
Home >> Interview Questions >> Unique Binary Search Trees

In this post, we will learn how to Generate all Possible Unique Binary Search Trees and will implement its solution in Java.

## Generate all Possible Unique Binary Search Trees

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

Example:
Input:
A = 3
Output:

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

## Unique Binary Search Trees Java Program

Approach 1

Recursive solution.

So the idea here is if we pick the i-th node as the root node then the left subtree will contain elements 1 to i-1 and the right subtree will contain elements i+1 to n. We are using recursive calls to get back all possible trees for left and right subtrees and combine them in all possible ways with the root node.

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<TreeNode>();
if(n==0) return res;
return generate(1,n);
}

public List<TreeNode> generate(int start, int end){
List<TreeNode> result = new ArrayList<TreeNode>();

//break condition
if(start>end){
return result;
}

for(int i=start; i<=end; i++){
//generate left tree
List<TreeNode> leftTree = generate(start, i-1);
//generate right tree
List<TreeNode> rightTree = generate(i+1, end);

//now add all left and right node to root node i
for(int j=0;j<leftTree.size(); j++){
TreeNode left = leftTree.get(j);
//add this left node to root and with all right node
for(int k=0;k<rightTree.size();k++){
TreeNode right = rightTree.get(k);
TreeNode node = new TreeNode(i);
node.left = left;
node.right = right;
}
}
}
return result;
}
}
```

Other Posts You May Like