Unique Binary Search Tree II Problem Solution

Unique Binary Search Tree II Problem: 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.

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

Unique Binary Search Tree II Problem Solution

Problem Solution In Python

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        
        if n<1:
            return []
        
        lst, dict_lst=[i+1 for i in range(n)], {tuple([]):[None]}
        
        def helper(lst):
            if tuple(lst) in dict_lst:
                return dict_lst[tuple(lst)] # need to be None for it to be used
            
            temp_tree=[]
            for i in range(len(lst)):
                left, right=lst[:i], lst[i+1:] 
                left_tree= helper(left)
                right_tree=helper(right)
                for x in left_tree:
                    for y in right_tree:
                        tree=TreeNode(lst[i])
                        tree.left=x
                        tree.right=y
                        temp_tree.append(tree)
                        
            dict_lst[tuple(lst)]=temp_tree
            return temp_tree
        
        return helper(lst)

Problem Solution In Java

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[][] dp = new List[n][n];
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = i+1;
        }
        if(n == 0){
            return new ArrayList<>();
        }
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                dp[i][j] = new ArrayList<>();
                List<TreeNode> one = new ArrayList<>();
                one.add(null);
                if(j == i){
                    TreeNode root = new TreeNode(nums[i]);
                    dp[i][j].add(root);
                    continue;
                }
                for(int k = i; k <= j; k++){
                    List<TreeNode> left = k==i ? one : dp[i][k-1];
                    List<TreeNode> right = k==j ? one : dp[k+1][j];
                    for(TreeNode l : left){
                        for(TreeNode r : right){
                            TreeNode root = new TreeNode(nums[k]);
                            root.left = l;
                            root.right = r;
                            dp[i][j].add(root);
                        }
                    }
                }
            }
        }
        return dp[0][n-1];
    }
}

Problem Solution In C++

map<int,vector<TreeNode*>> mp;
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n==0)
            return {};
     return cal(1,n);   
    }
    vector<TreeNode*> cal(int start,int end)
    {
        if(!mp[start*10+end].empty())
            return mp[start*10+end];
        if(start>end)
            return {NULL};
                      vector<TreeNode*> v;
        for(int i=start;i<=end;i++)
        {
            vector<TreeNode*> left=cal(start,i-1);
            vector<TreeNode*> right=cal(i+1,end);
            for(TreeNode * l:left)
            {
                for(TreeNode *r:right)
                {
                    TreeNode *current=new TreeNode(i);
                    current->left=l;
                    current->right=r;
                    v.push_back(current);
                }
            }
        }mp[start*10+end]=v;
        return v;
    }
};

Problem Solution In C

struct TreeNode** helper(int start,int end, int* returnSize){
    if(end<start){
        *returnSize=1;
        struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        ret[0]=NULL;
        return ret;
    }
    struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    *returnSize=0;
    for(int i=start;i<=end;i++){
        int leftReturnSize=0;
        int rightReturnSize=0;
        struct TreeNode** leftRet=helper(start,i-1,&leftReturnSize);
        struct TreeNode** rightRet=helper(i+1,end,&rightReturnSize);
        ret = realloc(ret,(leftReturnSize*rightReturnSize+*returnSize)*sizeof(struct TreeNode*));
        for(int left=0;left<leftReturnSize;left++){
            for(int right=0;right<rightReturnSize;right++){
                ret[(*returnSize)++]=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                ret[(*returnSize)-1]->val=i;
                ret[(*returnSize)-1]->left=leftRet[left];
                ret[(*returnSize)-1]->right=rightRet[right];
            }
        }
    }
    return ret;
}
struct TreeNode** generateTrees(int n, int* returnSize){
    if(n==1){
        struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        *returnSize=1;
        ret[0]=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        ret[0]->val=1;
        ret[0]->left=NULL;
        ret[0]->right=NULL;
    }
    if(n==0){
        *returnSize=0;
        return NULL;
    }
    return helper(1,n, returnSize);
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment