Unique Binary Search Trees
01 · Problem
Given an integer n, return how many structurally different binary search trees can be built that contain exactly the values 1 through n, each used once.
Two trees are considered different if their shapes or node placements differ. For example, with n = 2 there are two trees: 1 as the root with 2 as its right child, or 2 as the root with 1 as its left child.
02 · Examples
n = 3
5
Choosing 1, 2, or 3 as the root gives 2, 1, and 2 valid arrangements respectively, for a total of 5.
n = 1
1
A single node forms exactly one tree.
n = 4
14
Roots 1, 2, 3, 4 contribute 5, 2, 2, and 5 trees respectively, totalling 14.
03 · Constraints
- 011 <= n <= 19
- 02The answer fits in a 32-bit signed integer.
- 03Trees are counted by shape, with the values 1..n each used exactly once.
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.