allBSTs.scala

  /**
   * Compute all BSTs with nodes with values from 1 to `n`
   *
   * @return Roots of BSTs
   */
  def allBSTs(n: Int): Seq[Node] = {
    val memo = Array.ofDim[Seq[Node]](n + 1, n + 1)

    def all(from: Int, to: Int): Seq[Node] = {
      if (from > to) Seq(null)                 // Null child pointer
      else if (memo(from)(to) != null) memo(from)(to)
      else {
        if (from == to) Seq(Node(from))        // Leaf node
        else {
          // Consider all possible root values
          val roots = (from to to) flatMap { i =>
            for {
              left <- all(from, i - 1)         // Possible left children
              right <- all(i + 1, to)          // Possible right children
            } yield Node(i, left, right)
          }
          memo(from)(to) = roots
          roots
        }
      }

    }

    all(1, n)
  }