Last updated on October 9th, 2024 at 10:46 pm

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

Unique Binary Search Trees II 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]]

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];
    }
};

2. 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;    
    }
}

3. 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); 
};

4. 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)