Unique Binary Search Trees II - Recursion and memoization DP

Backtracking     Binary Search Tree     Binary Tree     C++     Dynamic Programming     Medium     Memoization     Recursion     Tree    

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

Solution:

We have the following recursive relation:

\[T(s,e) = \{ TreeNode(v=i,L=ta,R=tb) \forall ta \in T(s,i-1), tb \in T(i+1,e) \}\]

where $T(a,b)$ denotes answer for array containing BSTs containing values from $a$ to $b$. Our final answer is $T(1,n)$.

We will have repetition so let us add memoization. We will need 3-d array for memoization. Two indexes for $s, e$ and one for the array of treenodes $T(s,e)$.

 
class Solution {
    vector<vector<vector<TreeNode*>>> memo = vector<vector<vector<TreeNode*>>>(9, vector<vector<TreeNode*>>(9));
public:
    vector<TreeNode*> generateTrees(int n, int s=1) 
    {
        if (s>n || s<=0) return {NULL};
        if (memo[s][n].size()>0) return memo[s][n];
        if (s==n) return memo[s][n] = {new TreeNode(n)};
        vector<TreeNode*> res;
        for(int i=s; i<=n; i++)
        {
            vector<TreeNode*> leftTrees = generateTrees(i-1,s);
            vector<TreeNode*> rightTrees = generateTrees(n, i+1);
            for(TreeNode *left: leftTrees) for(TreeNode *right: rightTrees)
                res.push_back(new TreeNode(i, left, right));
        }
        return memo[s][n] = res;
    }
};