Unique Binary Search Trees II

1. Define the problem

Given an integer n, return every structurally unique binary search tree that stores exactly the values 1 through n, each returned as a level-order array with null marking a missing child. Use recursion : for every value i in the current range, make it the root, recursively build every possible left subtree from the values below i and every possible right subtree from the values above i, then combine each left/right pair under that root.

Constraints

1 ≤ n ≤ 8

Example

Inputn = 3

Output[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Explanation These are the five structurally different binary search trees that can store 1, 2, and 3.

2. Know the words first

In plain terms

Binary search tree: A binary tree where every node's left subtree holds only smaller values and its right subtree holds only larger values.
Level order: Listing tree node values top-to-bottom, left-to-right, the way LeetCode serializes trees, with null standing in for a missing child.

3. Visualize the solution

Pick each value as root, combine left and right subtree recursion

pos 11

pos 22

pos 33

Statusbuild([1..3]) tries i = 1

Value 1 becomes the root. Its left range [1..0] is empty (base case → null). The right range [2..3] must be built recursively.

What happens in this step

build(1, 3), i = 1
  left = build(1, 0)   → empty range, base case, returns [null]
  right = build(2, 3)  → not yet computed, recurse

Value 1 as root has no values below it, so its left subtree is the base case (an empty range returns [null]). Its right subtree spans [2..3] and must be built recursively before root 1 can be combined with anything.

Step 1 of 9

Steps to visualize

To build every BST over a range [start..end], try each value i in that range as the root.
Recursively build every possible left subtree from [start..i-1] and every possible right subtree from [i+1..end].
The base case is an empty range (start > end) — the only tree in an empty range is null.
Combine every left subtree with every right subtree under root i, adding each combination to the result.
The outer call for [1..n] collects every tree produced this way.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Pick each value as root, combine left and right subtree recursion

pos 11

pos 22

pos 33

Statusbuild([1..3]) tries i = 1

Value 1 becomes the root. Its left range [1..0] is empty (base case → null). The right range [2..3] must be built recursively.

What happens in this step

build(1, 3), i = 1
  left = build(1, 0)   → empty range, base case, returns [null]
  right = build(2, 3)  → not yet computed, recurse

Value 1 as root has no values below it, so its left subtree is the base case (an empty range returns [null]). Its right subtree spans [2..3] and must be built recursively before root 1 can be combined with anything.

Step 1 of 9

5. Solution

Solution

solution.tsTypeScript

function generateTrees(n) {
  if (n === 0) {
    return [];
  }

  function build(start, end) {
    if (start > end) {
      return [null]; // base case: empty range
    }
    const trees = [];
    for (let i = start; i <= end; i++) {
      const leftSubtrees = build(start, i - 1);
      const rightSubtrees = build(i + 1, end);
      for (const left of leftSubtrees) {
        for (const right of rightSubtrees) {
          trees.push({ val: i, left, right });
        }
      }
    }
    return trees;
  }

  function serialize(root) {
    if (root === null) {
      return [];
    }
    const result = [];
    const queue = [root];
    while (queue.length > 0) {
      const node = queue.shift();
      if (node === null) {
        result.push(null);
        continue;
      }
      result.push(node.val);
      queue.push(node.left === undefined ? null : node.left);
      queue.push(node.right === undefined ? null : node.right);
    }
    while (result.length > 0 && result[result.length - 1] === null) {
      result.pop();
    }
    return result;
  }

  return build(1, n).map(serialize);
}

Time: O(4ⁿ / n^1.5)
Space: O(4ⁿ / n^1.5)

6. Test cases

Test cases

Input	Expected	Covers
`n = 3`	`[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]`	example from the docstring
`n = 1`	`[[1]]`	base case, only one possible tree
`n = 2`	`[[1,null,2],[2,1]]`	two structurally different trees

Unique Binary Search Trees II