Unique Binary Search Trees
A medium BST interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- BST
- Sheets
- 1
- Core for
- 2 roles
The problem
Count the different shapes of binary search tree that can hold exactly the values 1 to n. The answers follow the Catalan numbers.
Example 1
- Input
- n=3
- Output
- 5
- Why
- There are 5 unique BSTs with values 1, 2, 3: (1,null,2,null,3), (1,null,3,2), (2,1,3), (3,1,null,null,2), (3,2,null,1).
Example 2
- Input
- n=1
- Output
- 1
- Why
- There is exactly 1 unique BST with a single node.
Example 3
- Input
- n=4
- Output
- 14
- Why
- There are 14 structurally unique BSTs with values 1 through 4.
Constraints
- 1 <= n <= 19
How to think about it
Updated 2026-09-29Any value i from 1 to n can serve as the root. Because of the BST property, the left subtree must be built entirely from the `i - 1` values smaller than i, and the right subtree from the `n - i` values larger than i. The total count for root i is the product of those independent possibilities, summing across all possible choices of i.
Approaches, worst first
Naive recursive divide and conquer
time O(3^n) · space O(n)
Implement the recurrence `G(n) = sum(G(i-1) * G(n-i))` directly with recursion. Computes the same subproblems over and over exponentially without memoization.
Dynamic programming array
time O(n^2) · space O(n)
Define `dp[k]` as the number of unique BSTs on k keys, with `dp[0] = dp[1] = 1`. Fill from 2 up to n using nested loops where the outer loop fixes the total size and the inner loop sums the product of left and right subtree counts across all root choices.
Direct Catalan formulaWrite this one
time O(n) · space O(1)
Calculate `C(n) = (2n)! / ((n + 1)! * n!)` directly using the iterative combination formula `C(n) = C(n-1) * 2(2n - 1) / (n + 1)`. Accumulates the result in 64-bit integers to avoid intermediate overflow.
Where people lose marks · 2
- Base case omission: `dp[0]` must equal 1, representing exactly one empty tree structure, otherwise multiplying left and right subtree counts zeroes out leaves.
- Intermediate integer overflow: when using the Catalan product formula, intermediate multiplication can exceed 32-bit integer limits before division even though the final answer fits.
The theory behind it
BST — the ground this problem stands on. All BST problems
What BST is
A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.
When to reach for it
Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.
How the pattern works
Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.
More BST problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .