Unique Binary Search Trees
The key idea
Pick each value as the root. Everything smaller goes left, everything larger goes right, so the left and right subtrees are independent sub-problems of the same shape. The count for n is the sum over every root of (ways to build the left subtree) times (ways to build the right subtree). This is the nth Catalan number.
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.
Two trees are considered structurally unique if their shapes differ — the values stored are fixed as 1 to n, so only the arrangement of nodes matters.
Constraints
- 1 <= n <= 19
Examples
Input: n = 3
Output: 5
Input: n = 1
Output: 1
Input: n = 4
Output: 14
Complexity
Time: O(n^2) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Dynamic Programming problems
- Best Time to Buy and Sell StockEASY
- Best Time to Buy and Sell Stock IIIHARD
- Best Time to Buy and Sell Stock IVHARD
- Best Time to Buy and Sell Stock with CooldownMEDIUM
- Best Time to Buy and Sell Stock with Transaction FeeMEDIUM
- Burst BalloonsHARD
- Climbing StairsEASY
- Coin ChangeMEDIUM
- Coin Change IIMEDIUM
- Combination Sum IVMEDIUM
- Counting BitsEASY
- Decode WaysMEDIUM