Unique Binary Search Trees

Intuitionwhy every tree is determined by its root split

A BST containing values 1 through n has one root. If the root is j, every value smaller than j must appear in the left subtree, and every value larger than j must appear in the right subtree. The left side contains j - 1 values, while the right side contains n - j values, so choosing root j creates two independent smaller BST problems.

The number of trees using root j is the number of possible left subtrees multiplied by the number of possible right subtrees. Multiplication is valid because every left choice can be paired with every right choice. Summing that product over all root values counts every structurally unique tree exactly once, because each tree has one and only one root.

That recurrence depends only on the number of values in a subtree, not on their actual labels. Let dp[i] be the number of structurally unique BSTs containing any i consecutive values. Then dp[i] can be built from already known values dp[0] through dp[i - 1]. The empty subtree contributes one possibility, which is why dp[0] starts at 1.

Approachturning every root choice into one DP transition

1. 1Create dp with indices 0 through n and initialize dp[0] to 1, because an empty subtree is one valid choice when a root has no values on one side.
2. 2Set dp[1] to 1, because a single value can form only one BST and the recurrence's base cases must be ready before computing larger sizes.
3. 3For each subtree size i from 2 through n, consider every possible root position j from 1 through i, because each position produces a distinct root split.
4. 4For root j, add dp[j - 1] multiplied by dp[i - j] to dp[i], because every valid left subtree can be paired independently with every valid right subtree.
5. 5Return dp[n], because the original problem contains exactly n values and dp[n] has accumulated the count from every possible root choice.

Complexitycounting transitions, not constructing trees

Annotated solutionC++ · bottom-up dynamic programming · one state per subtree size

#include <vector>
using namespace std;

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
};

The expression dp[j - 1] multiplied by dp[i - j] is the entire structural argument in code. The root itself uses one value, leaving j - 1 values on its left and i - j values on its right. The loops visit each possible root exactly once, so no tree is duplicated and no root split is omitted.

The Catalan formula is a useful O(n) alternativea mathematical optimization that removes the inner loop

The DP values are Catalan numbers, and consecutive Catalan numbers have a direct multiplicative relationship. Starting with C0 = 1, compute the next value with Ck = Ck-1 multiplied by 2(2k - 1), divided by k + 1. With n at most 19, a long long safely holds the intermediate arithmetic, while the final answer fits the required int return type.

#include <vector>
using namespace std;

class Solution {
public:
    int numTrees(int n) {
        long long trees = 1;

        for (int k = 1; k <= n; k++) {
            trees = trees * 2 * (2 * k - 1) / (k + 1);
        }

        return static_cast<int>(trees);
    }
};

This is an optimization, not merely a rearrangement: it changes the time bound from O(n^2) to O(n) and the extra space from O(n) to O(1). It buys a shorter state footprint but hides the root-splitting proof inside the Catalan identity. The DP version is usually easier to derive from the problem, while the formula is reasonable when the Catalan connection is familiar.

Common mistakestwo wrong lines that change the combinatorics