96: Unique Binary Search Trees

[kaif969]

Problem Number

96

Problem Title

Unique Binary Search Trees

LeetCode Link

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

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

Follow the below steps to Implement the idea:

• Create an array dp of size 20 (max 20 nodes as given)
• dp[0] = 1 and dp[1] = 1. (Base condition)
• Run for loop from i = 1 to i <= n and call recursion for each i.
• dp[n] += numTrees(i-1) * numTrees(n-i) , this line fills the complete dp array.
• If (dp[n]) return dp[n] , here we simply return the dp[n] if it's already filled so that we can avoid unnecessary recursion and calculations.
• finally, return dp[n] .

Intuition

Basic Intuition for this solution is using Dynamic Programming with memorization. For all possible values of i, consider i as root, then [1 . . . i-1] numbers will fall in the left subtree and [i+1 . . . N] numbers will fall in the right subtree.

Then all possible BST’s will be
numTrees(N) = summation of (numTrees(i-1)*numTrees(N-i)) where i lies in the range [1, N].

Solution in C++

class Solution {
public:
    int dp[20]{};
    int numTrees(int n) {
        if(n <= 1) return 1;
        if(dp[n]) return dp[n];
        for(int i = 1; i <= n; i++) 
            dp[n] += numTrees(i-1) * numTrees(n-i);
        return dp[n];
    }
};

[github-actions]

Hope so You have raised a valid issue, wait untill the owner will review the issue