Generic binary search tree

bst.scala

sealed trait Tree[+A]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object Leaf extends Tree[Nothing]

trait MinMax[A] {
  val min: A
  val max: A
}

implicit val intMM: MinMax[Int] = new MinMax[Int] {
  val min = Int.MinValue
  val max = Int.MaxValue
}

def isBST[A](tree: Tree[A])(implicit ord: Ordering[A], mm: MinMax[A]): Boolean = {
  import scala.Ordering.Implicits._

  def go(tree: Tree[A], max: A, min: A): Boolean = tree match {
    case Leaf => true
    case Node(value, left, right) =>
      value >= min && value <= max &&
            go(left, value, min) && go(right, max, value)
  }

  go(tree, mm.max, mm.min)
}

val notBst = Node(3, Node(5, Node(1, Leaf, Leaf), Node(4, Leaf, Leaf)), Node(2, Node(6, Leaf, Leaf), Leaf))
val bst = Node(10, Node(5, Leaf, Leaf), Leaf)
val bst2 = Node(6, Node(1, Node(1, Leaf, Leaf), Node(2, Leaf, Leaf)), Node(7, Leaf, Node(8, Leaf, Leaf)))

assert(!isBST(notBst))
assert(isBST(bst))
assert(isBST(bst2))