Unique Binary Search Trees II Medium 0 attempts
LeetCode ↗

Unique Binary Search Trees II

Medium TreeBinary TreeDFS LeetCode

Given n, generate all structurally unique BSTs that store values 1 to n.

Example: n = 3 → Output: 5 different BST structures

Sample Input
—
Sample Output
—
Constraints
  • 1 <= n <= 8
Topics
TreeBinary TreeDFS

Recursive Generation

function generateTrees(n) {
  function build(lo, hi) {
    if (lo > hi) return [null];
    const trees = [];
    for (let i = lo; i <= hi; i++) {
      for (const left of build(lo, i-1)) {
        for (const right of build(i+1, hi)) {
          trees.push({val: i, left, right});
        }
      }
    }
    return trees;
  }
  return n === 0 ? [] : build(1, n);
}

Time: O(4^n / n^(3/2)) | Space: O(4^n / n^(3/2))

Saved in this browser only. Private to you.

JavaScript