isSameBST.scala

  /**
   * Determine if both arrays of keys would form the same BSTs
   * without building the trees
   */
  def isSameBST(arr1: Array[Int], arr2: Array[Int]): Boolean = {

    // Compute the paths from root to node for each element
    def paths(arr: Array[Int]): Map[Int, String] = {
      var map = Map.empty[Int, String]

      // For each element
      arr.indices foreach { i =>
        var path = ""
        // Compare with elements before it
        (0 until i) foreach { j =>
          // If the path for the previous element is the same as the path for
          // the current element up to now, append the branch this element will take
          if (path == map(arr(j))) path += (if (arr(i) < arr(j)) 'L' else 'R')
        }
        // Save path for element
        map += arr(i) -> path
      }
      map
    }

    // Compute set of paths for each array and compare them
    paths(arr1) == paths(arr2)
  }