Unique Binary Search Trees

LeetCode Problem #96 (Medium)

Problem Statement

Given n, how many structurally unique BST's (binary search trees) that store values 1... n?

Testcase

Example 1:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Prerequisite Knowledge

Dynamic Programming

Refer to the Prerequisite Knowledge section in Coin Change 2:

Coin Change 2

Catalan Number

A sequence of non-negative numbers which commonly appears in combinatorial problems is known as Catalan Numbers. It often involves recursively defined objects.

Euler's Polygon Division Problem asks the question, "In how many ways can a regular n-gon be divided into n-2 triangles if different orientations are counted separately?"

In tree enumeration problems such as the one given above, the solution involves the Catalan Sequence.

Source: https://mathworld.wolfram.com/CatalanNumber.html

Formula

The nth Catalan Number is given by:

C(n) = (2n)! / ((n + 1)! * n!)

Catalan Series

The first few Catalan Numbers starting from 0 are:1, 1, 2, 5, 14, 42, 132, 429, 1430,...

Problem Explanation

In this problem, we must find the number of unique binary search trees that can be formed using a given number of nodes. In order to calculate the number of arrangements of nodes, we must choose the number of nodes in the left sub-tree and the number of nodes in the right sub-tree while considering each node as the root node.

Example

Consider n = 5. We can derive the following combinations:

1. root = 1->left nodes = 0 | right nodes = 4->f[0]*f[4]

2. root = 2->left nodes = 1 | right nodes = 3->f[1]*f[3]

3. root = 3->left nodes = 2 | right nodes = 2->f[2]*f[2]

4. root = 4->left nodes = 3 | right nodes = 1->f[3]*f[1]

5. root = 5->left nodes = 4 | right nodes = 0->f[4]*f[0]

Therefore, for n = 5 nodes, the total number of binary search trees can be represented as: f[5] = f[0]*f[4] + f[1]*f[3] + f[2]*f[2] + f[3]*f[1] + f[4]*f[0]

Generalized Formula

f[n] = f[0]*f[n-1] + f[1]*f[n-2] + ... + f[n-2]*f[1] + f[n-1]*f[0]

Algorithm

Bottom-Up DP Approach

The intuitive approach would be to use a bottom-up dynamic programming approach to construct unique binary search trees by using each node of the tree as a root node to derive different combinations.

The recursive formula to find the total number of combinations is:

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

1. Create a vector to store the solutions of each sub-problem.

2. Initialize dp[0] as 1 to account for the first solution with the root being set as 1.

3. For each node in the tree, compute the number of unique binary search trees that can be formed using this node as the root node, by applying the formula: dp[i] += dp[j-1] * dp[i-j].

Time Complexity: O(m*n)

Mathematical Approach

In this approach, we use the Nth Catalan Number formula to find the number of ways in which the nodes can be arranged to form unique binary search trees.

C(n) = (2n)! / ((n + 1)! * n!)

The reason for this can be attributed to the pattern that can be observed when we examine the number of nodes and the number of possible combinations that could be formed.

1. n = 1->c = 1

2. n = 2->c = 2

3. n = 3->c = 5

4. n = 4->c = 14

5. n = 5->c = 42

From the values of c that we have obtained, we can observe that the pattern is similar to that of the Catalan Numbers series as illustrated in the Prerequisite Knowledge section.

Time Complexity: O(n)

Code

Dynamic Programming Approach

int numTrees(int n) {
    vector<int> dp(n + 1, 0);
    // When 1 is set as root, 
    // left subtree = 0 children, right subtree = dp[n - 1] children
    // Set dp[0] = 1
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            // If k is set as the root node,
            // left subtree = (k - 1) children
            // right subtree = (n - k) children
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

Mathematical Approach

int numTrees(int n) {
    long long count = 1;
    for(int i = n + 1; i <= 2 * n; i++) {
        count = count * i / (i - n);
    }
    return count / (n + 1);
}