DAY 63 - Unique Binary Search Trees II
Tags: leetcode, algorithms, cpp, coding
Published: 2023-08-05 18:12:26

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](https://www.javatpoint.com/binary-search-tree)

> Example 1:

> ![Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m62asmfxapmmk3l5gd53.png)

## Question: [Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/description/)

_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:

> ![Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dnu8zb8v8gqhqr1x78m6.png)
> **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.