71. Unique Binary Search Trees II
mediumAsked at SnowflakeGenerate all structurally unique BSTs storing values 1..n. Snowflake asks this to test recursion-with-memoization and to set up a discussion on plan-tree generation — there are many ways to assemble n joins.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Snowflake loops.
- Glassdoor (2025-Q4)— Snowflake compiler-team uses this to lead into plan-tree enumeration.
- LeetCode Discuss (2025-08)— Reported at Snowflake new-grad screens.
Problem
Given an integer n, return all the structurally unique BSTs (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
Constraints
1 <= n <= 8
Examples
Example 1
n = 3[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]Example 2
n = 1[[1]]Approaches
1. Recursive generation by root choice
For each i in [start, end], recursively generate all left subtrees from [start, i-1] and right subtrees from [i+1, end]. Combine into new roots.
- Time
- Catalan(n) * n
- Space
- Catalan(n) * n
function generateTrees(n) {
function gen(start, end) {
if (start > end) return [null];
const trees = [];
for (let i = start; i <= end; i++) {
const lefts = gen(start, i - 1);
const rights = gen(i + 1, end);
for (const l of lefts) for (const r of rights) {
trees.push({ val: i, left: l, right: r });
}
}
return trees;
}
if (n === 0) return [];
return gen(1, n);
}Tradeoff: Catalan-number outputs, no way to be sub-Catalan.
2. Memoized recursion (optimal)
Cache results by (start, end). For small n the speedup is modest; for larger n it matters.
- Time
- Catalan(n) * n
- Space
- Catalan(n)
function generateTrees(n) {
const memo = new Map();
function gen(start, end) {
const key = `${start}-${end}`;
if (memo.has(key)) return memo.get(key);
if (start > end) return [null];
const trees = [];
for (let i = start; i <= end; i++) {
for (const l of gen(start, i - 1)) {
for (const r of gen(i + 1, end)) {
trees.push({ val: i, left: l, right: r });
}
}
}
memo.set(key, trees);
return trees;
}
if (n === 0) return [];
return gen(1, n);
}Tradeoff: Memoization shares subtree references across multiple trees — saves time and memory when shapes are identical but indices differ.
Snowflake-specific tips
Snowflake interviewers want the choose-root recursion and the Catalan-number intuition. Bonus signal: connect to plan tree enumeration — for an n-table join the planner might enumerate Catalan(n) plan shapes (different bracketing), and uses memoization keyed on the table subset to avoid redundant work.
Common mistakes
- Sharing subtree references unsafely — if a downstream user mutates, all trees that referenced it are corrupted (only a problem if you mutate; for read-only enumeration it's fine).
- Forgetting the base case (start > end -> [null]).
- Iterating without the null sentinel — special-cases left/right empty subtrees.
Follow-up questions
An interviewer at Snowflake may pivot to one of these next:
- Number of unique BSTs (LC 96).
- How does the planner enumerate join shapes?
- Catalan numbers and their combinatorial significance.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does memoization help?
Different ranges [a, b] and [c, d] of the same width have the same shape (just shifted values). Memoization on (start, end) avoids recomputing the same shapes.
How does this connect to plan enumeration?
An n-table join can be assembled in Catalan(n) bracketings. The planner enumerates via subset DP (memoizing best plan per subset), which is the costed version of this counting problem.