Skip to main content

68. Unique Binary Search Trees II

mediumAsked at Plaid

Generate all structurally unique BSTs with n nodes. Plaid asks this as a recursion + memoization warm-up before harder tree-construction problems on category-tree variants.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid construction-of-trees problem.

Problem

Given an integer n, return all the structurally unique BST's (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 build

For each root value v in [lo..hi]: build all left subtrees from [lo..v-1] and all right subtrees from [v+1..hi]; cross-product them as v's children.

Time
O(Catalan)
Space
O(Catalan)
function generateTrees(n) {
  function build(lo, hi) {
    if (lo > hi) return [null];
    const out = [];
    for (let v = lo; v <= hi; v++) {
      const lefts = build(lo, v - 1);
      const rights = build(v + 1, hi);
      for (const l of lefts) for (const r of rights) {
        out.push({ val: v, left: l, right: r });
      }
    }
    return out;
  }
  return build(1, n);
}

Tradeoff: Catalan-number output. For n=8 the count is 1430 trees, well within budget.

2. Memoized recursion

Cache build(lo, hi) results. Multiple call paths reach the same range.

Time
O(Catalan)
Space
O(Catalan)
// Same as above with a Map keyed by 'lo,hi'.
// Trees are shared by reference — fine if callers don't mutate.

Tradeoff: Shared subtrees save allocations but introduce aliasing — every output BST may share subtree nodes. Verify callers won't mutate.

Plaid-specific tips

Plaid grades this on whether you spot the BST recurrence: for each root, the left subtree is built from values strictly less, right subtree from values strictly greater. Bonus signal: discuss the aliasing trade-off of memoization — saves memory but couples outputs.

Common mistakes

  • Allowing v in left or right subtree — breaks BST property.
  • Forgetting the base case (lo > hi returns [null]).
  • Mutating shared nodes in the memoized version — corrupts other outputs.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Count, don't generate — Catalan numbers, LC 96.
  • Generate all balanced BSTs.
  • Construct a BST from a given sorted array (LC 108).

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 each root contribute left x right combinations?

Each left subtree is independent of each right subtree, so the count of v-rooted trees is |lefts| * |rights|.

Why is the count Catalan?

The recurrence count(n) = sum over v of count(v-1) * count(n-v) is exactly the Catalan recurrence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →