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 Sam K., 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

More Dynamic Programming practice problems

See all Dynamic Programming problems →