LeetCode 96: Unique Binary Search Trees

Problem Description

LeetCode Problem 96

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

Difficulty: Medium

Tags: math, dynamic programming, tree, binary search tree, binary tree

Rating: 96.17%

Solution Explanation

This problem is a perfect example of how dynamic programming can be used to solve seemingly complex counting problems. Let’s break down the solution step by step.

1. Understanding the Pattern

When building a BST with numbers from 1 to n:

• Any number i can be the root node
• All numbers less than i must go in the left subtree
• All numbers greater than i must go in the right subtree
• The structure of left and right subtrees determines the uniqueness

For example, with n = 3:

• When 1 is root:
  • Left subtree: empty
  • Right subtree: [2,3]
• When 2 is root:
  • Left subtree: [1]
  • Right subtree: [3]
• When 3 is root:
  • Left subtree: [1,2]
  • Right subtree: empty

2. The Dynamic Programming Approach

We use a DP array where:

• dp[i] represents the number of unique BSTs possible with i nodes
• Base cases:
  • dp[0] = 1 (empty tree is considered one valid configuration)
  • dp[1] = 1 (single node tree)

3. The Formula

For any number of nodes n, we can compute dp[n] using smaller subproblems:

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

Where:

• i is the current root node
• dp[i-1] is the number of possible left subtrees
• dp[n-i] is the number of possible right subtrees

4. Implementation

class Solution:
    def numTrees(self, n: int) -> int:
        # Initialize dp array
        dp = [0] * (n+1)
        dp[1] = dp[0] = 1
        
        # Build up the solution
        for nodes in range(2, n+1):
            for root in range(1, nodes+1):
                left_nodes = root - 1
                right_nodes = nodes - root
                dp[nodes] += dp[left_nodes] * dp[right_nodes]
        
        return dp[n]

5. Step-by-step Example

Let’s see how it works for n = 3:

1. Initialize: dp = [1, 1, 0, 0]

2. For nodes = 2:

   • root = 1: dp[2] += dp[0] * dp[1] = 1 * 1 = 1
   • root = 2: dp[2] += dp[1] * dp[0] = 1 * 1 = 1
   • Result: dp[2] = 2

3. For nodes = 3:

   • root = 1: dp[3] += dp[0] * dp[2] = 1 * 2 = 2
   • root = 2: dp[3] += dp[1] * dp[1] = 1 * 1 = 1
   • root = 3: dp[3] += dp[2] * dp[0] = 2 * 1 = 2
   • Result: dp[3] = 5

Complexity Analysis

• Time Complexity: $O(n^2)$
  • We have two nested loops: outer loop runs n times, inner loop also runs up to n times
• Space Complexity: $O(n)$
  • We only need an array of size n+1 to store our dp values

Mathematical Note

Interestingly, the numbers generated by this solution are known as Catalan numbers. The nth Catalan number can be calculated using the formula:

$C_n = \frac{1}{n+1}\binom{2n}{n}$

This explains why the problem has such a beautiful dynamic programming solution and why the pattern follows a predictable sequence: 1, 1, 2, 5, 14, 42, 132, …

Conclusion

This problem showcases how dynamic programming can break down a complex counting problem into manageable subproblems. The solution elegantly combines properties of binary search trees with the mathematical concept of Catalan numbers, demonstrating the deep connections between different areas of computer science and mathematics.