Skip to main content

72. Unique Binary Search Trees

mediumAsked at Ola

Count the number of structurally unique BSTs that store values 1..n.

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

Problem

Given an integer n, return the number of structurally unique BSTs which have 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. Enumerate all

Generate every BST as in II and count.

Time
O(Cn * n)
Space
O(Cn * n)
// reuse generateTrees(n).length

Tradeoff:

2. Catalan DP

G[n] = sum over i of G[i-1] * G[n-i] for i in 1..n; G[0] = G[1] = 1.

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

Tradeoff:

Ola-specific tips

Ola wants to see you recognize the Catalan recurrence; tie it to counting distinct ways to nest a fixed-size dispatcher subtree.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →