Dynamic Programming • Catalan Numbers

Unique Binary Search Trees

Given an integer n, return the number of structurally unique BSTs (Binary Search Trees) which has exactly n nodes of unique values from 1 to n.

Try Interactive Simulator

Overview

This problem is a classic application of Catalan Numbers. The number of unique BSTs with N nodes only depends on N, not on the actual values of the nodes.

The Root Selection

If we have `N` nodes, we can pick any node `i` (from 1 to N) to be the root. Once `i` is the root, all elements `< i` go to the left subtree, and `> i` go to the right.

The Multiplication

The number of nodes in the left subtree is `i - 1`. The number in the right subtree is `N - i`. The total combinations for root `i` is `dp[left] * dp[right]`.

The Loop

We sum up these combinations for every possible root `i` from 1 to N. We build this up from `n = 2` to `N` using a bottom-up DP approach.

Nodes N = -

Left Subtree

dp[0]

×

Right Subtree

dp[0]

DP Array (Catalan Sequence)

0

1

2

0

3

0

4

0

Code Tracker

:::

1let dp = new Array(n + 1).fill(0);

2dp[0] = 1;

3dp[1] = 1;

4for (let nodes = 2; nodes <= n; nodes++) {

5 for (let root = 1; root <= nodes; root++) {

6 let leftNodes = root - 1;

7 let rightNodes = nodes - root;

8 dp[nodes] += dp[leftNodes] * dp[rightNodes];

9 }

10}

11return dp[n];