95. Unique Binary Search Trees II

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

Constraints:

1 <= n <= 8

Intuition


Building all the left subtrees in that range and attaching
Let say 1 3 , It will have all trees possilble  from 1 to 3

This will be attach all the trees between 1 & 3 to left

and so on

We can use DP to memoize but no need as constraints are low

Links

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Video Links

https://leetcode.com/problems/unique-binary-search-trees-ii/solutions/1849266/c-detailed-explanation-recursive-tree-with-comments/

Approach 1:

Recursion

C++

class Solution {
public:
    vector<TreeNode*> buildTree(int start, int end) {
        vector<TreeNode*> ans;
  
        if(start > end) {
            ans.push_back(NULL);
            return ans;
        }

        for(int i = start; i <= end; ++i) {
            vector<TreeNode*> leftSubTree = buildTree(start, i - 1);
            vector<TreeNode*> rightSubTree = buildTree(i + 1, end);    
            /* 
            Building all the left subtrees in that range and attaching
            Let say 1 3 , It will have all trees possilble  from 1 to 3

            This will be attach all the trees between 1 & 3 to left

            and so on
            */
            for(int j = 0; j < leftSubTree.size(); j++) {
                for(int k = 0; k < rightSubTree.size(); k++) {
                    TreeNode* root = new TreeNode(i);   
                    root->left = leftSubTree[j];   
                    root->right = rightSubTree[k];  
                    ans.push_back(root);    
                }
            }
        }
            
        return ans;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        return buildTree(1, n);
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++