71. Unique Binary Search Trees II

mediumAsked at Snowflake

Generate 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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

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

Input

n = 3

Output

[[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]]

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Unique Binary Search Trees II and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →