LeetCode Problem 96

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree

Solution

LeetCode 96 - Unique Binary Search Trees

Problem Understanding

This problem asks us to determine how many structurally different Binary Search Trees, or BSTs, can be formed using the integers from 1 to n.

A Binary Search Tree has an important property:

• Every value in the left subtree is smaller than the root.
• Every value in the right subtree is larger than the root.

The input is a single integer n, which represents how many distinct values are available. The values themselves are fixed as the integers from 1 through n.

The output is the total number of unique BST structures that can be built using all n values exactly once.

The key detail is that we care about structure, not insertion order. Two BSTs are considered different if their shape differs, even if they contain the same values.

For example, when n = 3, the possible BST structures are:

• Root = 1, with all remaining nodes on the right
• Root = 2, with one node on each side
• Root = 3, with all remaining nodes on the left
• Additional structurally distinct subtree arrangements

This results in a total of 5 unique BSTs.

The constraint is:

1 <= n <= 19

This is a relatively small input size, which suggests that dynamic programming is feasible. However, naive recursive generation of every tree structure would still become very expensive because the number of BSTs grows rapidly.

An important observation is that the actual numeric values do not matter as much as the number of nodes in a subtree. Any sequence of k ordered values produces the same number of BST structures.

Some important edge cases include:

• n = 1, where only one tree is possible.
• Very small values such as n = 2, where both left-heavy and right-heavy trees must be counted separately.
• Larger values near 19, where recursive recomputation becomes expensive without memoization or bottom-up DP.

Approaches

Brute Force Approach

A brute-force solution would recursively generate every possible BST.

For each possible root value:

1. Recursively generate all possible left subtrees.
2. Recursively generate all possible right subtrees.
3. Combine every left subtree with every right subtree.

This approach is correct because every BST must choose exactly one root, and every valid left and right subtree combination produces a unique BST.

However, the same subtree sizes are recomputed repeatedly. For example, while solving for n = 5, the number of BSTs with 3 nodes may be calculated many times.

The recursive explosion makes the brute-force solution extremely inefficient.

Optimal Approach, Dynamic Programming

The key insight is that the number of unique BSTs depends only on how many nodes are in the tree, not on the actual values.

Suppose we define:

dp[i] = number of unique BSTs using i nodes

To compute dp[i], we try every node as the root.

If a root splits the tree into:

• left_nodes
• right_nodes

then:

total_trees = dp[left_nodes] * dp[right_nodes]

This multiplication works because every left subtree can pair with every right subtree.

We sum this across all possible root choices.

This creates a classic Dynamic Programming recurrence known as the Catalan Number recurrence.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Recursively generates all BST combinations repeatedly
Optimal	O(n²)	O(n)	Bottom-up DP using Catalan recurrence

Algorithm Walkthrough

1. Create a DP array named dp of size n + 1.

Each index i represents the number of unique BSTs that can be built using exactly i nodes. 2. Initialize the base cases.

We set:

dp[0] = 1
dp[1] = 1

dp[0] = 1 means an empty subtree counts as one valid configuration. This is important because a root may have no left or right child. 3. Iterate from 2 to n.

For each number of nodes nodes, compute the number of BSTs possible. 4. Try every node as the root.

If the root is positioned at root, then:

left_nodes = root - 1
right_nodes = nodes - root

5. Count subtree combinations.

The number of BSTs formed with this root is:

dp[left_nodes] * dp[right_nodes]

This multiplication works because every left subtree can combine independently with every right subtree. 6. Add the combinations to the total.

Accumulate all possible root configurations into dp[nodes]. 7. Return dp[n].

After filling the DP table, the answer for the original problem is stored at index n.

Why it works

The algorithm works because every BST can be uniquely defined by its root choice and the structure of its left and right subtrees.

For a fixed root:

• All smaller values must appear in the left subtree.
• All larger values must appear in the right subtree.

Since subtree structures are independent, the total number of trees for a root is the product of the number of left subtree possibilities and right subtree possibilities.

Summing across every possible root guarantees that every valid BST structure is counted exactly once.

Python Solution

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)

        dp[0] = 1
        dp[1] = 1

        for nodes in range(2, n + 1):
            total = 0

            for root in range(1, nodes + 1):
                left_nodes = root - 1
                right_nodes = nodes - root

                total += dp[left_nodes] * dp[right_nodes]

            dp[nodes] = total

        return dp[n]

The implementation begins by creating a DP array where each index stores the number of BSTs possible for that subtree size.

The base cases are initialized first. An empty tree and a single-node tree each have exactly one valid structure.

The outer loop iterates through every subtree size from 2 to n.

Inside that loop, every possible root position is tested. Choosing a root automatically determines how many nodes belong to the left subtree and how many belong to the right subtree.

The product:

dp[left_nodes] * dp[right_nodes]

counts every possible combination of left and right subtree structures.

After all root choices are processed, the total number of BSTs for that subtree size is stored in the DP table.

Finally, the algorithm returns dp[n].

Go Solution

func numTrees(n int) int {
    dp := make([]int, n+1)

    dp[0] = 1
    dp[1] = 1

    for nodes := 2; nodes <= n; nodes++ {
        total := 0

        for root := 1; root <= nodes; root++ {
            leftNodes := root - 1
            rightNodes := nodes - root

            total += dp[leftNodes] * dp[rightNodes]
        }

        dp[nodes] = total
    }

    return dp[n]
}

The Go implementation follows the same bottom-up dynamic programming strategy as the Python version.

Slices are used instead of Python lists. Integer arithmetic is safe because the constraints guarantee the result fits within Go's standard integer range for this problem.

Unlike Python, Go requires explicit variable declarations and uses camelCase naming conventions.

Worked Examples

Example 1

Input: n = 3

We initialize:

dp = [1, 1, 0, 0]

Now compute values step by step.

Computing dp[2]

Root	Left Nodes	Right Nodes	Calculation	Total
1	0	1	dp[0] × dp[1] = 1 × 1	1
2	1	0	dp[1] × dp[0] = 1 × 1	2

Result:

dp[2] = 2

DP state:

[1, 1, 2, 0]

Computing dp[3]

Root	Left Nodes	Right Nodes	Calculation	Total
1	0	2	1 × 2	2
2	1	1	1 × 1	3
3	2	0	2 × 1	5

Result:

dp[3] = 5

Final DP state:

[1, 1, 2, 5]

Answer:

5

Example 2

Input: n = 1

Initial DP:

dp = [1, 1]

No additional computation is needed because the base case already contains the answer.

Result:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	For each node count, we iterate through every possible root
Space	O(n)	The DP array stores results for subtree sizes from 0 to n

The outer loop runs n times, and the inner loop also runs up to n times in total across all iterations. This gives quadratic time complexity.

The space complexity is linear because only the DP table is stored.

Test Cases

solution = Solution()

assert solution.numTrees(1) == 1  # Single node
assert solution.numTrees(2) == 2  # Left-heavy and right-heavy trees
assert solution.numTrees(3) == 5  # Example from problem statement
assert solution.numTrees(4) == 14  # Standard Catalan value
assert solution.numTrees(5) == 42  # Larger DP accumulation
assert solution.numTrees(6) == 132  # Additional correctness check
assert solution.numTrees(7) == 429  # Confirms recurrence scaling
assert solution.numTrees(8) == 1430  # Medium-sized input
assert solution.numTrees(19) == 1767263190  # Upper constraint boundary

Test	Why
n = 1	Verifies smallest valid input
n = 2	Ensures both BST orientations are counted
n = 3	Matches official example
n = 4	Tests multiple recursive combinations
n = 5	Confirms DP accumulation correctness
n = 6	Verifies continued Catalan recurrence
n = 7	Checks larger combinational growth
n = 8	Tests medium-sized dynamic programming state
n = 19	Validates upper constraint handling

Edge Cases

One important edge case is n = 1. A naive implementation might accidentally treat a single-node tree as having zero combinations because there are no child subtrees. The DP base case correctly defines dp[1] = 1, ensuring the single valid BST is counted.

Another important case is handling empty subtrees. When the root is the smallest or largest value, one side of the tree contains zero nodes. If dp[0] were initialized to 0 instead of 1, all edge-root configurations would incorrectly contribute zero combinations. Defining the empty tree as one valid configuration fixes this issue.

A third important edge case involves larger values such as n = 19. Pure recursion without memoization would repeatedly recompute the same subtree counts and become extremely slow. The dynamic programming solution stores intermediate results so every subtree size is computed exactly once.

A subtle edge case is ensuring the left and right subtree sizes are calculated correctly. Off-by-one mistakes are common here. The implementation carefully uses:

left_nodes = root - 1
right_nodes = nodes - root

This guarantees that every node except the root is assigned to exactly one subtree.