Coding Problems

Unique Binary Search Trees | Leetcode 96

Welcome to our deep dive on Unique Binary Search Trees (Leetcode 96). This is a phenomenal Dynamic Programming problem that perfectly introduces Catalan numbers into algorithm math.

Problem Statement

Given an integer n, return the number of structurally unique BST's (binary search trees) which have exactly n nodes of unique values from 1 to n.

Example 1: n = 3 => Output: 5

Example 2: n = 1 => Output: 1

Approach: Dynamic Programming / Catalan Numbers O(N^2)

A BST maintains a strict structural rule: All nodes in the left subtree must be smaller than the root. All nodes in the right subtree must be larger than the root.

If we iterate through possible values of the Root Node i from 1 to n, then we know exactly how many nodes fall in its left subtree (i - 1), and exactly how many nodes fall in its right subtree (n - i).

Since the subtrees are structurally independent combinatorial problems, the total number of trees formed with i as the root is: (Number of Left Trees) * (Number of Right Trees)

  1. Suppose we select i = 2 as the root for n = 3.
    • Left Subtree Nodes: [1] (total 1 node).
    • Right Subtree Nodes: [3] (total 1 node).
    • G[1] * G[1] = 1 * 1 = 1.
  2. To find the total structure for n, we loop and add the products for every possible root!

The actual sequence is mathematically identical to the famous Catalan number sequence.

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        
        # Base Cases (an empty tree and a 1-node tree both count as 1 permutation)
        dp[0], dp[1] = 1, 1
        
        for nodes in range(2, n + 1):
            total = 0
            for root in range(1, nodes + 1):
                left_subtrees = root - 1
                right_subtrees = nodes - root
                
                # Combine combinations independently
                total += dp[left_subtrees] * dp[right_subtrees]
                
            dp[nodes] = total
            
        return dp[n]

Complexity Analysis

MetricComplexityExplanation
TimeO(N²)We compute the DP state iteratively for N sizes. Inside, we run an internal loop summing paths 1 to N. This mathematically simplifies to a triangular series summing to N².
SpaceO(N)The memory footprint strictly relies upon the 1D Array storing the N + 1 DP states explicitly generated.

Try it yourself!

Try this problem on LeetCode (96)

Related Internal Resources