### 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){ result.add(null); 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; result.add(node); } } } return result; } }

**Other Posts You May Like**

- Height of a Binary Tree
- How to Invert Binary Tree
- Count Unique Binary Search Trees Using Dynamic Programming
- Connect Nodes at the same level in Binary Tree
- Maximum Depth of N-ary Tree

## Comments

## Post a Comment