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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala