isBST

isbst.scala

case class Node(value: Int, left: Option[Node] = None, right: Option[Node] = None)

def isBST(n: Node): Boolean = {
  isBST(Option(n), Integer.MIN_VALUE, Integer.MAX_VALUE)
}

def isBST(nOpt: Option[Node],
          lowerBound: Int,
          upperBound: Int): Boolean = {
  nOpt match {
    case None => true
    case Some(n) => {
      (n.value > lowerBound &&
       n.value < upperBound &&
       isBST(n.left, lowerBound, n.value) &&
       isBST(n.right, n.value, upperBound))
    }
  }
}

val validTrees = Seq(
  null,
  Node(1),
  Node(3, Some(Node(1)), Some(Node(4))),
  Node(5, Some(Node(3, Some(Node(1)), Some(Node(4)))), Some(Node(8, Some(Node(7)), Some(Node(10))))))

val invalidTrees = Seq(
  Node(2, Some(Node(3)), Some(Node(4))),
  Node(2, Some(Node(1)), Some(Node(1))),
  Node(5, Some(Node(3, Some(Node(1)), Some(Node(10)))), Some(Node(7, Some(Node(6)), Some(Node(10))))),
  Node(5, Some(Node(3, Some(Node(1)), Some(Node(4)))), Some(Node(7, Some(Node(3)), Some(Node(10))))))

validTrees.foreach { t =>
  if (isBST(t)) {
    println("pass: valid tree " + t)
  } else {
    println("error: should be valid tree " + t)
  }
}

invalidTrees.foreach { t =>
  if (isBST(t)) {
    println("error: should be invalid tree " + t)
  } else {
    println("pass: invalid tree " + t)
  }
}