96_uniqueBinarySearchTrees.md

96. Unique Binary Search Trees 🌟🌟

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

MUST READ 👇:

• There are a few ways to solve this problem. I have explained all the solutions and approach to optimize it from Brute-Force to Dynamic Programming to solving using Catalan formula in: ✅ Simple Solution w/ Explanation | Optimization from Brute-Force to DP

1. Brute-Force                 ( Time: O(3^N), Space: O(N) )
2. Dynamic Programming - Memoization    ( Time: O(N^2), Space: O(N) )
3. Dynamic Programming - Tabulation     ( Time: O(N^2), Space: O(N) )
4. Catalan Numbers             ( Time: O(N), Space: O(1) )
5. Catalan Numbers (2nd Approach)      ( Time: O(N), Space: O(1) )

• C++ Easy & Clean Solution | Fastest | All (4+) Methods | Detailed Explanation & Comments

DP Solution(Tabulation)

• We have base conditions of dp[0] = dp[1] = 1.
• Then we calculate result for each number of nodes i from 2...n.
• For i nodes. we can consider each of the node j from 1...i as the root node.
• Considering the jth node as the root node in BST having total of i nodes, the result is summation for all j from 1...i of dp[j-1] * dp[i-j]. (Comparing to above solution dp[j-1] = numTrees(j-1) and dp[i-j]=numTrees(i-j))

Code

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; i++)
            for(int j = 1; j <= i; j++)
                dp[i] += dp[j-1] * dp[i-j];
        return dp[n];
    }
};