DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Unique Binary Search Trees

Problem statement

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*.

Problem statement taken from: https://leetcode.com/problems/unique-binary-search-trees.

Example 1:

Container

Input: n = 3
Output: 5
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 1
Output: 1
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= n <= 19
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force solution

The brute force approach is to generate all the possible BSTs and get the count. This approach will consume a lot of time when we increase n.

Dynamic Programming

With Dynamic Programming, we will reduce the scope of generating the BSTs and use mathematical concept to get the required result.

Let's take an example where n is 5. If node 2 is the root, then the left subtree will include 1 and the right subtree will include 3, 4, and 5. The possible number of combinations in the left subtree is 1, and in the right subtree is 5. We multiply 1 and 5. Similarly, if 3 is the root node, the possible number of combinations in the left subtree will be 2, and the number of combinations in the right subtree will be 2. So the total BST's when root node is 3 is 2*2 = 4. We add up all these combinations for each node 1 to n and return the required result.

A C++ snippet of the above approach is as below:

int numberOfBST(int n) {
    int dp[n + 1];
    fill_n(dp, n + 1, 0);

    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = dp[i] + (dp[i - j] * dp[j - 1]);
        }
    }

    return dp[n];
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(N^2) and space complexity is O(N).

Catalan numbers

[Catalan numbers (https://en.wikipedia.org/wiki/Catalan_number), in combinatorial mathematics, are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects.

It is denoted by Cn and the formula to calculate it is
(2n)! / ((n + 1)! * n!).

Let's check the algorithm to see how we can use this formula.

// numTrees function
- return catalan(2*n, n)

// catalan function
catalan(n , k)
- set result = 1

- if k > n - k
  - k = n - k

- for i = 0; i < k; i++
  - result *= (n - i)
  - result /= (i + 1)

- return result/(k + 1)
Enter fullscreen mode Exit fullscreen mode

The time complexity of this approach is O(N), and space complexity is O(1). Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    long long catalan(int n, int k) {
        long long result = 1;

        if(k > n - k) {
            k = n - k;
        }

        for(int i = 0; i < k; i++) {
            result *= (n - i);
            result /= (i + 1);
        }

        return result/(k + 1);
    }

    int numTrees(int n) {
        long long result = catalan(2*n , n );

        return (int) result ;

    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func catalan(n, k int) int {
    result := 1

    if k > n - k {
        k = n - k
    }

    for i := 0; i < k; i++ {
        result *= (n - i)
        result /= (i + 1)
    }

    return result/(k + 1)
}

func numTrees(n int) int {
    return catalan(2*n , n )
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var catalan = function(n, k) {
    let result = 1;

    if(k > n - k) {
        k = n - k;
    }

    for(let i = 0; i < k; i++) {
        result *= (n - i);
        result /= (i + 1);
    }

    return result/(k + 1);
}

var numTrees = function(n) {
    return catalan(2*n, n);
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

Input n = 4

Step 1: result = catalan(2*n , n )
               = catalan(2*4, 4)
               = catalan(8, 4)

// catalan function
Step 2: result = 1
        n = 8, k = 4

Step 3: if k > n - k
           4 > 8 - 4
           4 > 4
           false

Step 4: loop for i = 0; i < k
          0 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 1 * (8 - 0)
                  = 8

          result /= (i + 1)
                  = result / (i + 1)
                  = 8 / (0 + 1)
                  = 8

          i++
          i = 1

Step 5: loop for i < k
          1 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 8 * (8 - 1)
                  = 8 * 7
                  = 56

          result /= (i + 1)
                  = result / (i + 1)
                  = 56 / (1 + 1)
                  = 56 / 2
                  = 28

          i++
          i = 2

Step 6: loop for i < k
          2 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 28 * (8 - 2)
                  = 28 * 6
                  = 168

          result /= (i + 1)
                  = result / (i + 1)
                  = 168 / (2 + 1)
                  = 168 / 3
                  = 56

          i++
          i = 3

Step 7: loop for i < k
          3 < 4
          true

          result *= (n - i)
                  = result * (n - i)
                  = 56 * (8 - 3)
                  = 56 * 5
                  = 280

          result /= (i + 1)
                  = result / (i + 1)
                  = 280 / (3 + 1)
                  = 280 / 4
                  = 70

          i++
          i = 4

Step 8: loop for i < k
          4 < 4
          false

Step 9: return result/(k + 1)
               70/(4 + 1)
               70/5
               14

So we return the answer as 14.
Enter fullscreen mode Exit fullscreen mode

Discussion (0)