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.

Example: 1

Input: n = 3

Output: 5

Example: 2

Input: n = 1

Output: 1

Constraints:

• 1 <= n <= 19

Important observation for solving the problem:

• If we keep K as our root, then, all numbers lower than K will come in left subtree and all numbers greater than 1 will come in right subtree.
• Also, if we have X ways of forming left subtree and Y ways of forming right subtree, then, total number of trees rooted at K can be calculated as : ways(K) = ways(X) * ways(Y).
• The base case here is, if we have less than 1 nodes left, then we have only one way of forming such subtree.

Solving using recursion (TLE):

• We have nodes from range [1, n]. We will make it as [0, n - 1] for our convenience.
• Now suppose we take node 5 as our current root, then, the left subtree will contain nodes [0, 4] and right subtree will contain nodes [6, n - 1].
• We will solve this recursively, and when we reach our base case, we will return 1 as our answer.

Code using recursion: class Solution { public int numTrees(int n) { return recur(0, n - 1); } int recur(int l, int r) { // our base case if(l >= r) return 1; int ways = 0; // choosing i as the root node of current subtree for(int i = l; i <= r; i++) { ways = ways + recur(l, i - 1) * recur(i + 1, r); } return ways; } }

Caching the subproblems (TLE to Accepted):

• Now the above code gives TLE.
• This is because we are computing subproblems again and again.
• So we will just cache the results in an array or map, as we want to do.

Code using DP: class Solution { // array to store results of subproblems Integer[][] dp; public int numTrees(int n) { dp = new Integer[n][n]; return recur(0, n - 1); } int recur(int l, int r) { if(l >= r) return 1; // checking if we have already solved this subproblem // if yes, we will return it's answer if(dp[l][r] != null) return dp[l][r]; int ways = 0; for(int i = l; i <= r; i++) { ways = ways + recur(l, i - 1) * recur(i + 1, r); } // storing the result of the current subproblem // so that it can be used later on dp[l][r] = ways; return ways; } }