Unique Binary Search Trees II Medium 0 attempts
LeetCode ↗

Unique Binary Search Trees II

Medium TreeBinary TreeDFS LeetCode

For a given integer n, construct every distinct binary search tree that can be formed from the keys 1 through n, and return all of them.

Input Format
Implement generateTrees(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Each returned tree is displayed as a level-order array. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
n = 2
Output
[[1,null,2],[2,1]]

Example 2

Input
n = 1
Output
[[1]]
Constraints
  • 1 <= n <= 8
Test Cases (2)
Case 1
Args: [2] Expected: [[1,null,2],[2,1]]
Case 2
Args: [1] Expected: [[1]]
Topics
TreeBinary TreeDFS

Recursive Generation

javascript
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(n × Cn) as a loose upper bound, where Cn is the nth Catalan number | Space: O(n × Cn), including returned trees

Saved in this browser only. Private to you.

JavaScript