Skip to main content

96. Unique Binary Search Trees

medium

Count structurally unique BSTs that can be built from n nodes with values 1..n. The Catalan-number DP — pick a root, count left and right subtree shapes, multiply.

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

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

Explanation: The 5 unique BST shapes with values 1, 2, 3.

Example 2

Input
n = 1
Output
1

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Fix a root value k in 1..n. Left subtree has k-1 nodes, right subtree has n-k nodes.

Hint 2

Count of BSTs of size n = sum over k of (count of size k-1) * (count of size n-k).

Hint 3

This is the Catalan number recurrence C(0) = 1, C(n) = sum_{i=0..n-1} C(i) * C(n-1-i).

Solution approach

Reveal approach

Define the subproblem dp[i] = the number of structurally unique BSTs that can be built from i nodes (the labels don't matter once you fix an in-order traversal, so the count depends only on size). The recurrence relation is dp[i] = sum over k in 0..i-1 of dp[k] * dp[i-1-k] — pick a root, the left subtree gets k of the remaining nodes, the right gets i-1-k, and the two subtrees are independent. Base cases dp[0] = 1 (empty tree counts) and dp[1] = 1. Fill dp[2..n] iteratively. Return dp[n]. Two nested loops give O(n^2) time and O(n) space. The closed-form is the n-th Catalan number C(2n, n) / (n+1), but the DP is what interviewers expect and is the clearer derivation.

Complexity

Time
O(n^2)
Space
O(n)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • tree-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Unique Binary Search Trees and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →