LeetCode 96: Unique Binary Search Trees Solution in Python Explained

Problem Statement

In LeetCode 96, you’re given an integer n. Your task is to return the total number of unique BSTs that can store values 1 through n, where each tree follows BST properties (left < root < right). This is a counting companion to LeetCode 95: Unique Binary Search Trees II, which generates the trees, and differs from traversal tasks like LeetCode 94: Binary Tree Inorder Traversal.

Constraints

• 1 <= n <= 19

Example

Let’s see some cases:

Copy codeInput: n = 3
Output: 5
Explanation: 5 unique BSTs with nodes 1,2,3:
<ul>
<li>[1,null,2,null,3]</li>
<li>[1,null,3,2]</li>
<li>[2,1,3]</li>
<li>[3,1,null,null,2]</li>
<li>[3,2,null,1]</li>
</ul>

Copy codeInput: n = 1
Output: 1
Explanation: 1 BST: [1]

Copy codeInput: n = 2
Output: 2
Explanation: 2 BSTs: [1,null,2], [2,1]

These examples show we’re counting unique BSTs.

Understanding the Problem

How do you solve LeetCode 96: Unique Binary Search Trees in Python? Take n = 3. We need the number of unique BSTs with nodes 1,2,3—there are 5. Each BST has a root, with left and right subtrees forming smaller BSTs. This isn’t a string decoding task like LeetCode 91: Decode Ways; it’s about combinatorial counting. We’ll use: 1. Dynamic Programming Bottom-Up: O(n²) time, O(n) space—our best solution. 2. Catalan Number Formula: O(n) time, O(1) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Dynamic Programming Bottom-Up Approach (Primary)

Explanation

Dynamic Programming Bottom-Up builds the count of unique BSTs by defining dp[i] as the number of unique BSTs with i nodes. For each root, the number of trees is the product of left and right subtree counts. This approach is the best solution due to its clarity, efficiency, and intuitive breakdown into subproblems, aligning with BST construction logic.

For n = 3:

• dp[0] = 1 (empty tree).
• dp[1] = 1 (one node).
• dp[2] = 2 (two nodes).
• dp[3] = 5 (dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]).

Step-by-Step Example

Example 1: n = 3

Goal: Return 5.

• Start: dp = [1,0,0,0] (length 4).
• Step 1: i = 1.
• Root 1: Left 0, Right 0 → dp[0]*dp[0] = 1*1 = 1.
• dp[1] = 1.
• Step 2: i = 2.
• Root 1: Left 0, Right 1 → dp[0]*dp[1] = 1*1 = 1.
• Root 2: Left 1, Right 0 → dp[1]*dp[0] = 1*1 = 1.
• dp[2] = 1 + 1 = 2.
• Step 3: i = 3.
• Root 1: Left 0, Right 2 → dp[0]*dp[2] = 1*2 = 2.
• Root 2: Left 1, Right 1 → dp[1]*dp[1] = 1*1 = 1.
• Root 3: Left 2, Right 0 → dp[2]*dp[0] = 2*1 = 2.
• dp[3] = 2 + 1 + 2 = 5.
• Finish: Return dp[3] = 5.

Example 2: n = 1

Goal: Return 1.

• Start: dp = [1,0].
• Step 1: i = 1.
• Root 1: Left 0, Right 0 → 1*1 = 1.
• dp[1] = 1.
• Finish: Return 1.

Example 3: n = 2

Goal: Return 2.

• Start: dp = [1,0,0].
• Step 1: i = 1.
• dp[1] = 1.
• Step 2: i = 2.
• Root 1: 1*1 = 1.
• Root 2: 1*1 = 1.
• dp[2] = 1 + 1 = 2.
• Finish: Return 2.

How the Code Works (Dynamic Programming Bottom-Up) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef numTrees(n: int) -> int:
    # Line 1: Initialize DP array
    dp = [0] * (n + 1)
    # Creates array of zeros with length n+1 (e.g., [0,0,0,0] for n=3)
    # dp[i] = number of unique BSTs with i nodes

    # Line 2: Base case for 0 nodes
    dp[0] = 1
    # dp[0] = 1, an empty tree has 1 way (no nodes)
    # Foundation for building counts

    # Line 3: Build DP array for each length
    for i in range(1, n + 1):
        # i = number of nodes (e.g., 1 to 3)
        # Computes dp[i] for each size

        # Line 4: Try each value as root
        for j in range(i):
            # j = index of root (0-based, e.g., 0 to 2 for i=3)
            # Represents root value 1 to i in 1-based terms

            # Line 5: Calculate trees with j nodes on left, i-j-1 on right
            dp[i] += dp[j] * dp[i - j - 1]
            # Multiplies number of left subtrees by right subtrees
            # e.g., i=3, j=0: dp[0]*dp[2] = 1*2 (root 1)
            # j=1: dp[1]*dp[1] = 1*1 (root 2)
            # j=2: dp[2]*dp[0] = 2*1 (root 3)
            # dp[3] accumulates: 2 + 1 + 2 = 5

    # Line 6: Return total number of unique BSTs
    return dp[n]
    # Returns dp[n] (e.g., dp[3] = 5)
    # Final count of unique BSTs for n nodes

This detailed breakdown clarifies how the bottom-up DP approach efficiently computes the count of unique BSTs.

Alternative: Catalan Number Formula Approach

Explanation

Catalan Number Formula uses the mathematical property that the number of unique BSTs for n nodes is the n-th Catalan number: C(n) = (2n)! / (n!(n+1)!). This is a direct computation, avoiding explicit tree construction, making it a concise alternative.

For n = 3:

• C(3) = (6)! / (3!*4!) = 720 / (6*24) = 5.

Step-by-Step Example (Alternative)

For n = 3:

• Step 1: Compute C(3).
• Numerator: 6! = 720.
• Denominator: 3! = 6, 4! = 24, 6*24 = 144.
• 720 / 144 = 5.
• Finish: Return 5.

How the Code Works (Catalan Formula)

Copy codedef numTreesCatalan(n: int) -> int:
    def factorial(k: int) -> int:
        result = 1
        for i in range(1, k + 1):
            result *= i
        return result

    numerator = factorial(2 * n)
    denominator = factorial(n) * factorial(n + 1)
    return numerator // denominator

Complexity

• Dynamic Programming Bottom-Up:
• Time: O(n²) – nested loops over n.
• Space: O(n) – DP array.
• Catalan Number Formula:
• Time: O(n) – factorial computation.
• Space: O(1) – constant space.

Efficiency Notes

Dynamic Programming Bottom-Up is the best solution with O(n²) time and O(n) space, offering a clear, intuitive approach that’s practical for the constraint (n ≤ 19)—Catalan Number Formula is faster at O(n) but involves large factorials, risking overflow for larger n without optimization.

Key Insights

• DP Subproblems: Left and right subtree counts.
• Catalan: Mathematical shortcut.
• BST Property: Drives uniqueness.

Additional Example

For n = 4:

• Goal: 14.
• DP: dp[4] = dp[0]*dp[3] + dp[1]*dp[2] + dp[2]*dp[1] + dp[3]*dp[0] = 5 + 2 + 2 + 5 = 14.

Edge Cases

• n = 1: 1.
• n = 2: 2.
• n = 0: Not applicable (constraint n ≥ 1).

Both solutions handle these well.

Final Thoughts

LeetCode 96: Unique Binary Search Trees in Python is a captivating counting challenge. The Dynamic Programming Bottom-Up solution balances efficiency and understanding, while the Catalan Number Formula offers a sleek alternative. Want more? Try LeetCode 95: Unique Binary Search Trees II for generating trees or LeetCode 94: Binary Tree Inorder Traversal for traversal. Ready to practice? Solve LeetCode 96 on LeetCode with n = 3, aiming for 5—test your skills now!