Catalan Numbers: The Counting Pattern Behind Many Interview Problems

Count the binary search trees with n nodes. Count the balanced strings of n pairs of parentheses. Count the ways to triangulate a polygon. These look unrelated, but the answers are the same sequence: 1, 1, 2, 5, 14, 42, 132, ... These are the Catalan numbers.

The recurrence

Pick what goes first, such as the root of a BST, and split the remaining items into an independent left and right part:

C(0) = 1, C(n) = Σ C(i) · C(n − 1 − i) for i in 0..n−1

def catalan(n):
    c = [0] * (n + 1)
    c[0] = 1
    for m in range(1, n + 1):
        c[m] = sum(c[i] * c[m - 1 - i] for i in range(m))
    return c[n]

That's O(n²). The closed form C(n) = (2n choose n) / (n + 1) gives O(n) with big integers, or with a modular inverse when the problem asks for the answer modulo a prime.

Recognising a Catalan problem

The structure is "choose a split point; the two sides are independent and of the same kind". Classic instances:

• Number of structurally unique BSTs with keys 1..n.
• Valid parentheses strings with n pairs.
• Full binary trees with n + 1 leaves.
• Ways to triangulate a convex polygon with n + 2 sides.
• Monotonic lattice paths that never cross the diagonal (the Dyck path view).
• Stack-sortable permutations and valid push/pop sequences.

Why (2n choose n)/(n + 1)?

The reflection argument: of all (2n choose n) lattice paths, the "bad" ones that cross the diagonal correspond one-to-one to paths ending at a reflected point, and there are (2n choose n+1) of them. The difference simplifies to (2n choose n)/(n + 1). You won't usually need the proof, but one sentence about reflection is impressive.

Counting vs generating

If the interviewer asks you to list all valid parentheses or all BSTs, the output size is Catalan, so no algorithm beats O(C(n) · n). State that when discussing complexity: it shows you know the answer's size bounds the work.

Disclosure: from the makers of an AI interview assistant (Linkjob AI).