Explanation for the Problem

For anyone trying to solve this problem, it is important to realize the nature of binary search trees (BST). As a BST, each node will have elements which are lesser than itself in the left subtree and elements that are greater than itself in the right subtree. Also, note that the problem is asking for structurally unique BSTs, which means where you have to count distinct structure formations, not permutations of the same structure.

Given an integer $n$, we are asked to output the number of structurally unique BSTs that use values from $1$ to $n$. For instance, if $n=3$, we have 5 unique BSTs, illustrated in the problem description.

Approach

The solution approach is based on dynamic programming and understanding of BST properties.

Dynamic Programming

The basic idea of Dynamic Programming (DP) is to divide the problem into subproblems, solve these subproblems, and reuse their solutions to solve the original problem.

Here, we define $G(i)$ to represent the number of unique BSTs that we can construct with $i$ distinct values.

We would build up the value of $G(i)$ from $i = 0$, $i = 1$, etc, until $i = n$. At each step, we would calculate G(i) as the sum of F(i, j) for j = 0 up to i, where F(i,j) represents the number of unique BSTs that have j as a root.

But how do we compute F(i,j)?

Recall what a BST implies: for a sequence of length i, if we select the jth number as the root, numbers <= j will form the left subtree, and numbers > j will form the right subtree. Therefore, F(i,j) can be computed as the Cartesian product of the number of BSTs formed by the left and right subtrees, i.e., F(i,j) = G(j) * G(i-j-1).

So, for example, to compute G(3), we compute F(3, 0) = G(0)*G(2), F(3,1) = G(1)*G(1), and F(3,2) = G(2)*G(0), and sum these up.

Solutions

Let's go ahead and create the solutions as required.

Python

1
2python
3class Solution:
4    def numTrees(self, n: int) -> int:
5        G = [0]*(n+1)
6        G[0] = 1
7        G[1] = 1
8
9        for i in range(2, n+1):
10            for j in range(1, i+1):
11                # Use BST property to compute F(i, j) = G(j-1) *  G(i-j)
12                G[i] += G[j-1] * G[i-j]
13        return G[n]

The Python solution follows the exact approach that we discussed above initializing G to all 0's and keeping G[0] = G[1] = 1 always.

Java

1
2java
3class Solution {
4    public int numTrees(int n) {
5        int[] G = new int[n + 1];
6        G[0] = 1;
7        G[1] = 1;
8
9        for (int i = 2; i <= n; ++i) {
10          for (int j = 1; j <= i; ++j) {
11            G[i] += G[j - 1] * G[i - j];
12          }
13        }
14        return G[n];
15    }
16}

The Java solution also uses the same dynamic programming approach.

JavaScript

1
2javascript
3var numTrees = function(n) {
4    const G = new Array(n + 1).fill(0);
5    G[0] = 1;
6    G[1] = 1;
7
8    for(let i = 2; i <= n; ++i) {
9        for(let j = 1; j <= i; ++j) {
10            G[i] += G[j - 1] * G[i - j];
11        }
12    }
13    return G[n];
14};

The JavaScript solution also uses the same approach.

C++

1
2cpp
3class Solution {
4public:
5    int numTrees(int n) {
6        vector<int> G(n + 1, 0);
7        G[0] = 1;
8        G[1] = 1;
9
10        for (int i = 2; i <= n; ++i) {
11          for (int j = 1; j <= i; ++j) {
12            G[i] += G[j - 1] * G[i - j];
13          }
14        }
15        return G[n];
16    }
17};

The C++ solution also uses the same approach.

C#

1
2csharp
3public class Solution {
4    public int NumTrees(int n) {
5        int[] G = new int[n + 1];
6        G[0] = 1;
7        G[1] = 1;
8
9        for (int i = 2; i <= n; ++i) {
10          for (int j = 1; j <= i; ++j) {
11            G[i] += G[j - 1] * G[i - j];
12          }
13        }
14        return G[n];
15    }
16}

The C# solution also uses the same approach.

Wrapping up

We learned about a problem of constructing BSTs and solved it using Dynamic Programming in Python, C++, Java, JavaScript, and C# languages. Understanding the properties of BSTs were crucial to come up with an efficient approach to the problem.This approach utilizes Dynamic Programming to create a table G, that stores the results of the subproblems. The entry G[i] in this table stores the number of unique BST's that can be constructed using 'i' nodes. The entries of G are computed in a bottom-up manner using previously computed subproblems. Each G[i] is computed by taking the sum of G[j-1] * G[i-j] for all 'j' from 1 to 'i'.

The Dynamic Programming approach ensures an optimal solution by breaking the problem into simpler subproblems and using these already computed subproblems to compute the original problem. This approach significantly improves the efficiency of the algorithm, reducing the time complexity from O(n!) in the brute force approach to O(n^2) in the Dynamic Programming approach.

It's always recommended to try and understand the nature of the problem before attempting to solve it. This would often be the key to solve many problems in competitive programming and real-world programming situations. Hence, are able to understand complex data types, recognizing and implementing Dynamic Programming patterns and under the hood operations of data structure operations would be a great asset for a software developer.

Although the problem here is related to constructing binary search trees; the application of the problem-solving approach could be extended to many other problems in computer science and software development. So it is always good to keep your learning and curiosity alive!