Unique Binary Search Trees II LeetCode Solution

Last updated on January 29th, 2025 at 02:19 am

Here, we see a Unique Binary Search Trees II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming, Tree

Level of Question

Medium

Unique Binary Search Trees II LeetCode Solution

Unique Binary Search Trees II LeetCode Solution

1. 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]]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Tree Depth First Search”. This is because the problem involves recursively constructing all possible binary search trees (BSTs) for a given range of numbers. The recursion explores all possible left and right subtrees for each root value, which is characteristic of a depth-first traversal.

3. Code Implementation in Different Languages

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

3.2 Unique Binary Search Trees II 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.3 Unique Binary Search Trees II 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); 
};

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

4. Time and Space Complexity

Space Complexity
C++O(n2) + O(n)
JavaO(n)
JavaScriptO(n)
PythonO(n)
Scroll to Top