Scala by Example — Chapter 07

/**
 * Exercise 7.2.2 Consider the following definitions representing trees of
 * integers. These definitions can be seen as an alternative representation of
 * IntSet:
 *
 *    abstract class IntTree
 *    case object EmptyTree extends IntTree
 *    case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
 *
 * Complete the following implementations of function contains and insert for
 * IntTree's.
 *
 *    def contains(t: IntTree, v: Int): Boolean = t match {}
 *    def insert(t: IntTree, v: Int): IntTree = t match {}
 */

abstract class IntTree
case object EmptyTree extends IntTree
case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree

def contains(t: IntTree, v: Int): Boolean = t match {
  case EmptyTree                           => false
  case Node(elem, _, _) if (elem == v)     => true
  case Node(elem, left, _) if (elem < v)   => contains(left, v)
  case Node(elem, _, right) if (elem > v)  => contains(right, v)
}

def insert(t: IntTree, v: Int): IntTree = t match {
  case EmptyTree => new Node(v, EmptyTree, EmptyTree)
  case Node(elem, left, _) if (v < elem) => new Node(elem, insert(left, v), right)
  case Node(elem, left, right) => new Node(elem, left, insert(right, v))
}