Skip to main content

71. Unique Binary Search Trees II

mediumAsked at Ola

Generate every structurally unique BST that stores values 1..n.

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

Problem

Given an integer n, return all structurally unique BSTs that store values 1 to n. Return the answer in any order.

Constraints

  • 1 <= n <= 8

Examples

Example 1

Input
n = 3
Output
5 trees

Example 2

Input
n = 1
Output
1 tree

Approaches

1. Brute generate permutations

Insert every permutation into a BST and dedup.

Time
O(n! * n)
Space
O(n!)
// generate every permutation 1..n; insert into BST; dedup by serialization

Tradeoff:

2. DFS by root choice

For each root r, recursively build all left subtrees from [lo, r-1] and right subtrees from [r+1, hi].

Time
O(Cn * n)
Space
O(Cn * n)
function generateTrees(n) {
  if (n === 0) return [];
  const build = (lo, hi) => {
    if (lo > hi) return [null];
    const out = [];
    for (let r = lo; r <= hi; r++) {
      for (const L of build(lo, r-1)) {
        for (const R of build(r+1, hi)) {
          out.push({ val: r, left: L, right: R });
        }
      }
    }
    return out;
  };
  return build(1, n);
}

Tradeoff:

Ola-specific tips

Ola interviewers like clean range-DFS shapes; tie it to enumerating dispatcher decision trees over a numbered zone range.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →