How do you approach Unique Binary Search Trees?

Each value can be the root; the left/right subtrees are independent subproblems.

What are common mistakes on Unique Binary Search Trees?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Unique Binary Search Trees

MediumAlgorithms

Description

Given an integer n, return the number of structurally unique binary search trees that store values 1 through n.

Example 1

Input: n = 3

Output: 5

Explanation: There are 5 unique BSTs over {1,2,3}.

Example 2

Input: n = 1

Output: 1

Explanation: Only one tree.

Constraints

- 1 <= n <= 19

Unique Binary Search Trees: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 2-step hint ladder

Each value can be the root; the left/right subtrees are independent subproblems.
This is the Catalan number recurrence: dp[i] = sum of dp[j-1]*dp[i-j].

The optimal approach

Show the approach: The approach

Catalan DP. With `j` as the root, the left subtree holds `j-1` nodes and the right holds `i-j`. Summing the products over all roots gives `dp[i] = Σ dp[j-1]·dp[i-j]`, the i-th Catalan number.

Time: O(n²). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.