Unique Binary Search Trees II

Description

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1         3     3      2      1
\       /     /      / \      

3     2     1      1   3      2
/     /       \                 

2     1         2                 3

 

Constraints:

• 0 <= n <= 8

Solution(javascript)

function TreeNode(val) {
  this.val = val
  this.left = null
  this.right = null
}
const generateTrees = (n) => {
  if (n === 0) {
    return []
  }
  const numbers = new Array(n).fill(0).map((v, index) => index + 1)
  const memo = {}
  const compose = (number, left, right) => {
    const result = []
    for (let i = 0; i < left.length; i++) {
      for (let j = 0; j < right.length; j++) {
        const node = new TreeNode(number)
        node.left = left[i]
        node.right = right[j]
        result.push(node)
      }
    }
    return result
  }
  const aux = (list = []) => {
    const key = list.toString()
    if (memo[key] !== undefined) {
      return memo[list.toString()]
    }
    if (list.length === 0) {
      return [null]
    }
    memo[key] = list.reduce(
      (acc, number) => {
        acc.push(
          ...compose(
            number,
            aux(list.filter(x => x < number)),
            aux(list.filter(x => x > number)),
          ),
        )
        return acc
      },
      [],
    )
    return memo[key]
  }
  return aux(numbers)
}