DAY 63 - Unique Binary Search Trees II

Welcome to DAY 63. Today we will diverge once again into the Data Structure Trees and look at some more questions. Today we are going to do a question on Binary Search Trees.

To explain BST in a single line would be it's a tree where it's left node and all it's children in that subtree contains lesser value than the parent node and right value has more value than the parent node.

Every subtree in a BST is also a BST.

To read more on BST's read on Binary Search Trees

Example 1:

Question: Unique Binary Search Trees II

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

Intuition:

• To find all the possible permutations of BSTs with n nodes, we can select one node as the root node and split n - 1 nodes between the left and right subtrees in all the possible ways.
• Let's say we place a node with value index as the root node and place index - 1 nodes having values from 1 to index - 1 in the left subtree.
• If index == 1, the left child is null(Case-1).
• Similarly, we place the remaining n - index nodes having values from index + 1 to n in the right subtree. (If index == n, the right child is null).
• Similarly if we follow the recursively method and apply it on leftSubtrees and rightSubtrees. We can get those individually.
• We implement a recursive function helper(start, end) where start and end correspond to the range of node values that should be present in the BSTs created by this call.
• For a root node with value index, we will find all the left subtrees using leftSubTrees = helper(start, index - 1) and also compute all the right subtrees using rightSubTrees = helper(index + 1, right).
• Finally, we iterate over all pairs between leftSubTrees and rightSubTrees and create a new root with value index for each pair.

Algorithm and Code:

Algorithm:

• The helper function is a recursive function that takes the range of numbers [start, end] and a map dp to store the already computed results for subproblems.

• The function returns a vector of TreeNode pointers, representing all possible BSTs that can be formed using the numbers in the given range.

• The function uses dynamic programming with memoization to avoid redundant calculations for overlapping subproblems. The map dp is used to store previously computed results for specific ranges of numbers.

• The base cases for the recursion are when start > end, indicating an empty range, in which case a single NULL TreeNode is added to the result vector.

• If the result for the current range [start, end] is already present in the dp map, it is directly returned.

• Otherwise, for each number root in the range [start, end], the function recursively calculates all possible left subtrees for the range [start, root-1] and all possible right subtrees for the range [root+1, end].

• For each combination of left and right subtrees, a new TreeNode with value root is created, and its left and right children are set to the left and right subtrees, respectively.

• The new TreeNode is added to the result vector, representing one possible BST with the current root node.

• The function returns the result vector containing all possible BSTs for the given range [start, end].

• The generateTrees function is the main function that calls the helper function with the range [1, n] to generate all possible BSTs using the numbers from 1 to n.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> helper(int start, int end, map<pair<int,int>,vector<TreeNode*>>& dp){
        vector<TreeNode*> res;
        if(start > end){
            res.push_back(NULL);
            return res;
        }

        if(dp.find(make_pair(start,end)) != dp.end()){
            return dp[make_pair(start,end)];
        }

        for(int root = start; root <=end; root++){
            vector<TreeNode*> leftSubtrees = helper(start,root-1,dp);
            vector<TreeNode*> rightSubtrees = helper(root+1,end,dp);

            for(auto lt : leftSubtrees){
                for(auto rt : rightSubtrees){
                    TreeNode* new_node = new TreeNode(root);
                    new_node->left = lt;
                    new_node->right = rt;
                    res.push_back(new_node);
                }
            }
        }
        return dp[make_pair(start,end)] = res;
    }
    vector<TreeNode*> generateTrees(int n) {
        map<pair<int,int>,vector<TreeNode*>> dp;
        return helper(1,n,dp);
    }
};

Complexity Analysis:

• Time: O(4^n/sqrt(n))
• Space: O(4^n / (n^(3/2))) due to the storage of all possible BST structures.