Count of Structurally Unique BSTs (How Many Shapes Exist)

• Root-choice argument – choosing value j as root leaves j-1 values on the left and N-j on the right.
• Independence – left and right subtrees are structurally independent, so multiply their counts.
• Catalan recurrence – count[k] = sum of count[j-1] * count[k-j] for j from 1 to k.
• Base cases – count[0] = 1 (empty tree) and count[1] = 1 (single node).
• Complexity – O(N^2) time, O(N) space, far cheaper than the exponential cost of generating all trees.

What is the Count of Structurally Unique BSTs problem?

Given a positive integer N, count the number of structurally unique binary search trees that can store the values 1 through N. Two BSTs are structurally different if they have different shapes, even if they store the same values. You must return only the count, not the actual trees.

This is a counting DP problem, much cheaper than the generation problem (which is exponential).

How does the root-choice recurrence work?

If you choose value j (where 1 <= j <= N) as the root, then values 1 through j-1 go into the left subtree and values j+1 through N go into the right subtree. The BST property determines this partition uniquely.

Because the two subtrees are structurally independent, the number of trees with root j is count[j-1] * count[N-j]. Summing over all possible roots gives the total count.

package com.bank.service;

public class TierShapeCounter {

    public static int countUniqueBSTs(int n) {
        int[] count = new int[n + 1];
        count[0] = 1; // empty tree
        count[1] = 1; // single node

        for (int k = 2; k <= n; k++) {
            for (int root = 1; root <= k; root++) {
                count[k] += count[root - 1] * count[k - root];
            }
        }
        return count[n];
    }

    public static void main(String[] args) {
        for (int n = 1; n <= 7; n++) {
            System.out.println("N=" + n + " -> " + countUniqueBSTs(n) + " unique BSTs");
        }
    }
}

N=1 -> 1 unique BSTs
N=2 -> 2 unique BSTs
N=3 -> 5 unique BSTs
N=4 -> 14 unique BSTs
N=5 -> 42 unique BSTs
N=6 -> 132 unique BSTs
N=7 -> 429 unique BSTs

Why is this the Catalan number?

The recurrence C(n) = sum of C(j-1) * C(n-j) for j from 1 to n, with C(0) = 1, is exactly the definition of the n-th Catalan number. The closed-form is C(n) = (2n)! / ((n+1)! * n!), but the DP recurrence avoids computing large factorials.

Catalan numbers appear in many combinatorial problems: the number of balanced parenthesisations, the number of full binary trees, the number of ways to triangulate a polygon, and more.

// Closed-form Catalan (prone to overflow for large n)
public static long catalanClosedForm(int n) {
    long result = 1;
    for (int i = 0; i < n; i++) {
        result = result * 2 * (2 * i + 1) / (i + 2);
    }
    return result;
}

How is counting different from generating?

| Aspect | Counting (this problem) | Generating (Unique BSTs II) |
|---|---|---|
| Output | A single integer | A list of all tree roots |
| Time | O(N^2) | O(4^N / sqrt(N)) exponential |
| Space | O(N) | O(4^N / sqrt(N)) for all trees |
| Approach | DP on counts | Recursive tree construction |
| When to use | Only count needed | Must enumerate all shapes |

Counting is quadratic; generating is exponential. Whenever only the count is needed, avoid generation.

// Generating is exponential - avoid when only count is needed
// public List<TreeNode> generateTrees(int n) { ... }
// For N=19, there are 1,767,263,190 unique BSTs - enumeration is impractical

What are the edge cases?

• N = 0 – one unique BST: the empty tree. count[0] = 1.
• N = 1 – one unique BST: a single node.
• Large N – Catalan numbers grow past int range. For N = 19, the count is 1,767,263,190 which fits in int, but N = 20 gives 6,564,120,420 which requires long.

// For large N, use long to avoid overflow
public static long countUniqueBSTsLong(int n) {
    long[] count = new long[n + 1];
    count[0] = 1;
    count[1] = 1;
    for (int k = 2; k <= n; k++) {
        for (int root = 1; root <= k; root++) {
            count[k] += count[root - 1] * count[k - root];
        }
    }
    return count[n];
}

What are common mistakes?

The most common mistake is setting count[0] = 0 instead of 1.

// WRONG: count[0] = 0
// An empty subtree must count as 1 possibility (the "nothing" tree)
// Otherwise the product count[left] * count[right] becomes 0
// whenever one side is empty, killing all counts

// CORRECT: count[0] = 1
count[0] = 1; // the empty tree is one valid structure

Another mistake is confusing this problem with generating all trees and writing an exponential solution when only the count is needed.

What is the time and space complexity?

The outer loop runs N-1 times and the inner loop runs up to k times, giving O(N^2) total iterations. Each iteration does O(1) work. Space is O(N) for the count array. This is efficient enough to handle N in the thousands.

What should a senior engineer know?

A senior engineer should know the connection between counting and generating. Counting uses the Catalan recurrence in O(N^2), while generating requires building all trees in exponential time. The Catalan number has a closed-form formula, but the DP avoids overflow issues from large factorials.

For very large N (millions), even the quadratic DP becomes slow. The closed-form with modular arithmetic can compute the result in O(N) time, which matters for competitive programming. In production banking analytics, N is small (number of tiers), so the quadratic DP is more than sufficient.

// BigInteger for very large N
import java.math.BigInteger;

public static BigInteger countUniqueBSTsBig(int n) {
    BigInteger[] count = new BigInteger[n + 1];
    count[0] = BigInteger.ONE;
    for (int k = 1; k <= n; k++) {
        count[k] = BigInteger.ZERO;
        for (int root = 1; root <= k; root++) {
            count[k] = count[k].add(count[root - 1].multiply(count[k - root]));
        }
    }
    return count[n];
}