Skip to main content

72. Unique Binary Search Trees

mediumAsked at Snowflake

Count the number of structurally unique BSTs storing values 1..n. Snowflake asks this for the Catalan-number DP — directly relevant to counting alternative plan shapes for n-table joins.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this for plan-enumeration intuition.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-I screens.

Problem

Given an integer n, return the number of structurally unique BST's (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. Recursive without memo

f(n) = sum over root i: f(i-1) * f(n-i).

Time
O(2^n)
Space
O(n)
function numTrees(n) {
  if (n <= 1) return 1;
  let total = 0;
  for (let i = 1; i <= n; i++) total += numTrees(i - 1) * numTrees(n - i);
  return total;
}

Tradeoff: Exponential. Mention only to reject.

2. Bottom-up DP (optimal)

dp[k] = number of unique BSTs with k nodes. dp[k] = sum over root i: dp[i-1] * dp[k-i].

Time
O(n^2)
Space
O(n)
function numTrees(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let k = 2; 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) DP. Result equals the nth Catalan number; closed-form C(2n, n) / (n+1) is O(n) but harder to remember.

Snowflake-specific tips

Snowflake interviewers want the Catalan-number connection: 'this is the nth Catalan number'. Bonus signal: discuss why planners can't afford to enumerate all Catalan-many plans, and how subset DP (cost-based) collapses to O(3^n) instead of O(Catalan(n)).

Common mistakes

  • Recursing without memoization — exponential.
  • Off-by-one on the dp index (dp[0] = 1 represents empty subtree).
  • Trying the closed-form C(2n,n)/(n+1) without handling overflow — for n <= 19 it fits in Number.

Follow-up questions

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

  • Unique BSTs II (LC 95) — actually generate them.
  • Catalan numbers in other contexts (balanced parens, mountain paths).
  • Cost-based plan enumeration: O(3^n) vs O(Catalan(n)).

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 dp[0] = 1?

An empty BST counts as 1 way (the null subtree). Without it, dp[k] for any leaf root would compute 0 * something.

How does this connect to plan enumeration?

An n-table join has Catalan(n) plan shapes. Cost-based DP that only keeps the best plan per subset reduces to O(3^n). Counting all shapes (without costs) gives Catalan; costing dramatically prunes.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →