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

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.