Skip to main content

Unique Binary Search Trees | leetcode 96 solution

 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

solution:



❌ Solution - I (Brute-Force) [TLE]

Let's start by trying to solve the problem in Brute-Force manner. To form structurally unique BST consisting of n nodes, we can start by taking any of the node 1...n as the root node. Let the chosen root node be i. Then, we have a BST where the root node is i, the left child consist of all nodes from 1...i-1 (since left sub-tree must have only less than root's value) and right child consist of all nodes from i+1...n.

              1            1                   2                    3               3

          \            \                 / \                  /               /

             3             2              1   3                2               1

               /               \                                 /                 \

              2                 3                              1                    2

                     i = 1                   i = 2                       i = 3           

(i = root node)

Now, we need to realize that the number of structurally unique BST formable with nodes having value i+1...n is equal to the number of structurally unique BST formable with nodes having value i+1-i...n-i = 1...n-i. Why? Because we only need to find BST which are structurally unique irrespective of their values and we can form an equal number of them with nodes from 1...n or 2...n+1 or n...2n-1 and so on. So, the number only depends on number of nodes using which BST is to be formed.

Now, when we choose i as root node, we will have nodes from 1...i-1 (i-1 nodes in total) in left sub-tree and nodes from i+1...n (n-i nodes in total) in the right side. We can then form numTrees(i-1) BSTs for left sub-tree and numTrees(n-i) BSTs for the right sub-tree. The total number of structurally unique BSTs formed having root i will be equal to product of these two, i.e, numTrees(i-1) * numTrees(n-i). The same can be followed recursively till we reach base case - numTrees(0) = numTrees(1) = 1 because we can form only a single empty BST and single node BST in these cases respectively.

The final answer will be summation of answers considering all 1...n as root nodes.

          3                          2                         1              
          / \                        / \                      /   \     
numTrees(2) numTrees(0)    numTrees(1) numTrees(1)   numTrees(0) numTrees(2)             
        i = 3                      i = 2                     i = 1          

                      i
 =>              /   \
        numTrees(i-1) numTrees(n-i)

With that in mind, we have the following -

C++

class Solution {
public:
    int numTrees(int n) {
        if(n <= 1) return 1;
        int ans = 0;
        for(int i = 1; i <= n; i++)
            ans += numTrees(i-1) * numTrees(n-i);
        return ans;
    }
};

Python

class Solution:
    def numTrees(self, n: int) -> int:
        if n <= 1: return 1
        return sum(self.numTrees(i-1) * self.numTrees(n-i) for i in range(1, n+1))

Time Complexity : O(3N), where N is the given number of nodes in BST. Read here for proof.

Space Complexity : O(N), the maximum recursive stack depth.

✔️ Solution - II (Dynamic Programming - Memoization)

The above approach times out due to lots of unnecessary repeated calculation.

f(i) = numTrees(i)

                                                                 f(5)

__________________________________|____________________________________________  

                  ↙                            ↓                ↓                ↓                 ↘

        (f(0)*           f(4))                 f(1)*f(3)        f(2)*f(2)        f(3)*f(1)          f(4)*f(0)

    _____________|_____________             ⬆️          ⬆️  ⬆️         ⬆️                 ⬆️

            ↙        ↓        ↓         ↘     

        f(0)f(3)     f(1)f(2)   f(2)f(1)   f(3)f(0)      

  ______|_____       ⬆️ ⬆️        ⬆️

          ↙      ↓     ↘

      f(0)f(2) f(1)f(1) f(2)f(1)

          __|__         ⬆️ 

      ↙       ↘

     f(0)f(1)  f(1)f(0)

In the above diagram, drawing out even the partial recursion tree for the above approach, we can find that there are many redundant repeated calculations. We can instead store or memoize these result and later avoid repeated calculations over and over again.

The approach and code will be very similar. The only change is every time we calculate the result for numTrees(i), we store the result in dp[i] and only then return it. After that, each time we encounter dp[i] that's already calculated, we can directly return the result. This way, we won't solve for the same numTrees(i) multiple times.

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];

    }

};

Python

class Solution:

    @cache

    def numTrees(self, n: int) -> int:

        if n <= 1: return 1

        return sum(self.numTrees(i-1) * self.numTrees(n-i) for i in range(1, n+1))

Time Complexity : O(N2)

Here we calculate numTrees(i) (for 1<=i<=N) only once and memoize it which will take O(N). For calculating each of numTrees(i), we need N iterations to calculate numTrees(0)*numTrees(i) + numTrees(1)*numTrees(i-1) + numTrees(2)*numTrees(i-2)+ ... + numTrees(i)*numTrees(0). Thus, the overall time complexity becomes O(N*N).

Space Complexity : O(N), required for recursion and memoization

✔️ Solution - III (Dynamic Programming - Tabulation)

We can also solve it using iterative dynamic programming. Again, the logic is similar to above with slight change in approach that we start from base conditions instead of other way around.

  • We have base conditions of dp[0] = dp[1] = 1.

  • Then we calculate result for each number of nodes i from 2...n one after another.

  • For i nodes. we can consider each of the node j from 1...i as the root node of BST.

  • Considering the jth node as the root node in BST having total of i nodes, the final result is summation of dp[j-1] * dp[i-j], for all j from 1...i. (Comparing to above solution dp[j-1] = numTrees(j-1) and dp[i-j]=numTrees(i-j))

C++

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];

    }

};

Python

class Solution:

    def numTrees(self, n: int) -> int:

        dp = [0]*(n+1)

        dp[0], dp[1] = 1, 1

        for i in range(2, n+1):

            for j in range(1, i+1):

                dp[i] += dp[j-1] * dp[i-j]

        return dp[n]

Time Complexity : O(N2), we iterate over the range i=[2, n] and iteratively calculate dp[i]. The total number of operations performed equals 2+3+4+5..n = (n*(n+1)/2)-1 ≈ O(N2)

Space Complexity : O(N), required to store the results in dp

✔️ Solution - IV (Catalan Numbers)

Observing the series we get above for various numTrees(n), we see that it is infact a series of popular numbers known as Catalan Numbers. This approach is hard to get unless you are already familiar with catalan numbers and probably wont be expected in interview either. But I am mentioning this approach as another possible and more efficient solution to this question.

We can use the following formula for calculating catalan numbers Cn to calculate the result in O(N) time complexity -

We will use 1st equation of above image with binomial coefficient function - ncr in C++ to avoid overflow. In python, we can directly calculate factorial as it can handle long numbers

C++

class Solution {
public:
    long ncr(int n, int r) {
        long ans = 1;
        for(int i = 0; i < r; i++) {
            ans *= n-i;
            ans /= i+1;
        }
        return ans;  
    }
    int numTrees(int n) {
        return ncr(2*n, n) / (n + 1);
    }
};

👉 Further Simplified!

Python

class Solution:
    def numTrees(self, n: int) -> int:
        return factorial(2*n) // (factorial(n)*factorial(n+1))

Time Complexity : O(N) The ncr function runs in O(N) time. In python, the factorial function takes O(N) time as well.

Space Complexity : O(1)

✔️ Solution - V (Catalan Numbers - 2)

The Catalan Numbers also follow the below recurrence relation -

This can be said to be a kind of dynamic programming approach where our next result depends only on previous one. This is slightly easier to implement in code than the 1st formula for catalan numbers.

C++

class Solution {
public:
    int numTrees(int n) {
        long ans = 1;
        for(int i = 0; i < n; i++)
            ans *= (4*i+2) / (i+2.);
        return ans;
    }
};

Python

class Solution:
    def numTrees(self, n: int) -> int:
        return int(prod((4*i+2) / (i+2) for i in range(n)))

Time Complexity : O(N)

Space Complexity : O(1)


Labels:

Comments

Post a Comment

Popular posts from this blog

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...
Post a Comment
Read more

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...
Post a Comment
Read more

Regular Expression Matching Leetcode Solution

Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a"  Output: false  Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*"  Output: true  Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*"  Output: true  Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase Englis...
Post a Comment
Read more