Skip to main content

67. Unique Binary Search Trees

mediumAsked at Vercel

Count the number of structurally unique BSTs that store values 1..n. Vercel asks this as a clean introduction to Catalan numbers via DP — same recurrence shape as their build-order-counting for module dependency trees.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen DP warm-up.
  • LeetCode Discuss (2026-Q1)— Listed in Vercel interview prep notes.

Problem

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.

Constraints

  • 1 <= n <= 19

Examples

Example 1

Input
n = 3
Output
5

Example 2

Input
n = 1
Output
1

Approaches

1. Generate all trees and count

Recursively build all BSTs; return the count.

Time
exponential
Space
exponential
// Catalan-many trees; impractical past n=10.

Tradeoff: Wastes work — we only need the count, not the trees.

2. DP via Catalan recurrence (optimal)

G(n) = sum over root i of G(i-1) * G(n-i). Build bottom-up: G(0)=1, then for each k from 1..n, sum G(i-1)*G(k-i) for i in 1..k.

Time
O(n^2)
Space
O(n)
function numTrees(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= k; i++) {
      dp[k] += dp[i - 1] * dp[k - i];
    }
  }
  return dp[n];
}

Tradeoff: O(n^2) with O(n) space. The recurrence is the Catalan number formula in disguise.

Vercel-specific tips

Vercel grades the recurrence articulation. Bonus signal: identifying these as Catalan numbers (G(n) = C_n) and noting that the closed form C_n = (2n choose n) / (n+1) gives O(n) but with combinatorial complexity that's overkill.

Common mistakes

  • Confusing 'unique BSTs' with 'unique binary trees' — for BSTs, structure is determined by which values go left/right; values 1..n only differ by structure.
  • Off-by-one in the sum bounds (i from 1 to k inclusive).
  • Forgetting dp[0] = 1 (empty tree counts as 1 way).

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Unique Binary Search Trees II (LC 95) — generate the trees.
  • Closed-form Catalan number computation.
  • Number of unique BSTs with k as the root.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is dp[0] = 1?

An empty subtree has exactly one configuration (it doesn't exist). This base case is essential for the multiplication in the recurrence to work.

Connection to Catalan?

The recurrence G(n) = sum G(i-1) * G(n-i) is the Catalan-number recurrence. So G(n) = C_n. Verifying: C_3 = 5, matching example.

Practice these live with InterviewChamp.AI

Drill Unique Binary Search Trees and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →