NUHMAN.com

Introduction

LeetCode 96: Unique Binary Search Trees is a problem where you are asked to calculate how many structurally unique binary search trees (BSTs) can be made using n distinct nodes, labeled from 1 to n. This problem is a classic example of dynamic programming and is directly related to the Catalan number formula.

A binary search tree (BST) is a tree where for each node:

• The left subtree contains only nodes with values less than the node’s value.
• The right subtree contains only nodes with values greater than the node’s value.

In this article, we will explore an efficient dynamic programming approach to solve this problem.

Problem Statement

Given an integer n, return the number of structurally unique BST's (binary search trees) that store values 1 to n.

Example:

go

Input: n = 3
Output: 5
Explanation: Given n = 3, there are 5 unique BSTs:
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

In this example, when n = 3, there are 5 unique BSTs that can be formed using values 1, 2, and 3.

Approach:

Dynamic Programming Approach:

This problem can be solved using Dynamic Programming (DP), where the number of unique BSTs for n nodes is computed iteratively based on previously computed values.

1. Base Case:

• There is exactly one unique BST that can be formed with 0 or 1 node:
• For n = 0, the number of unique BSTs is 1 (the empty tree).
• For n = 1, the number of unique BSTs is 1 (a single node tree).

1. Recursive Relation:

• For any node i from 1 to n, consider i as the root of the tree. Then:
• The left subtree consists of values from 1 to i-1 (which is i-1 nodes).
• The right subtree consists of values from i+1 to n (which is n-i nodes).
• The total number of unique BSTs for a given n is the sum of products of the number of unique BSTs for the left and right subtrees across all i:

java

dp[n] = Σ dp[i-1] * dp[n-i] for i = 1 to n

1. Dynamic Programming Table:

• Use an array dp[] where dp[i] represents the number of unique BSTs that can be formed using i nodes.
• Fill this array iteratively for i from 2 to n.

Go Implementation

Dynamic Programming Solution

go

func numTrees(n int) int {
    if n == 0 {
        return 0
    }
    
    // dp[i] will store the number of unique BSTs that can be formed with i nodes
    dp := make([]int, n+1)
    
    // Base case: 1 way to form a BST with 0 or 1 node
    dp[0], dp[1] = 1, 1
    
    // Fill the dp array for i = 2 to n
    for i := 2; i <= n; i++ {
        // Calculate dp[i] based on previous values
        for j := 1; j <= i; j++ {
            dp[i] += dp[j-1] * dp[i-j]
        }
    }
    
    // Return the result for n nodes
    return dp[n]
}

Explanation:

1. Dynamic Programming Table Initialization:

• dp[0] is initialized to 1 because there is one way to form an empty tree (i.e., no nodes).
• dp[1] is initialized to 1 because there is exactly one BST that can be formed with a single node.

1. Filling the DP Table:

• For each i from 2 to n, the value dp[i] is calculated by summing the product of dp[j-1] (number of unique BSTs in the left subtree) and dp[i-j] (number of unique BSTs in the right subtree) for every j from 1 to i.
• This is done because j represents the position of the root node, and the left and right subtrees are formed from the remaining nodes.

1. Final Result:

• After filling the dp array, the number of unique BSTs that can be formed using n nodes is stored in dp[n].

Time and Space Complexity

MetricComplexityTime ComplexityO(n^2)Space ComplexityO(n)

Where:

• Time Complexity: The time complexity is O(n^2) because for each value of i from 2 to n, we compute the sum for all j from 1 to i.
• Space Complexity: The space complexity is O(n) due to the space required for the dp array.

Edge Cases

1. n = 0:

• Input: n = 0
• Output: 1
• Explanation: There is exactly one way to form a BST with zero nodes (an empty tree).

1. n = 1:

• Input: n = 1
• Output: 1
• Explanation: There is exactly one way to form a BST with one node (a single node tree).

1. Large n:

• As n increases, the number of unique BSTs grows rapidly. The dynamic programming approach efficiently handles this by building solutions from smaller subproblems.

Conclusion

LeetCode 96: Unique Binary Search Trees is an important problem that demonstrates the power of dynamic programming. By using a bottom-up approach to fill a DP table, we can efficiently calculate the number of unique BSTs for a given n nodes. This approach is much more efficient than a brute force recursive solution and works well even for large values of n.

The solution has a time complexity of O(n^2) and space complexity of O(n), making it an optimal approach for this problem.