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