Immutable binary search trees

gistfile1.scala

sealed trait BST[+K, +V]

object BST {
  def apply[K: Ordering, V](k: K, v: V): Node[K, V] = Node(k, v, Empty, Empty)

  case object Empty extends BST[Nothing, Nothing]
  case class Node[K, V](key: K, value: V, left: BST[K, V], right: BST[K, V])(implicit ord: Ordering[K]) extends BST[K, V] {
    def get(item: K): Option[V] = search(item, this)
    def +(kv: (K, V)): Node[K, V] = insert(kv._1, kv._2, this)

    private def search(item: K, node: BST[K, V]): Option[V] = {
      import ord._
      node match {
        case Empty => None
        case Node(k, v, leftNode, rightNode) =>
          if (item < k) search(item, leftNode)
          else if (item > k) search(item, rightNode)
          else Some(v)
      }
    }

    private def insert(item: K, itemValue: V, node: BST[K, V]): Node[K, V] = {
      import ord._
      node match {
        case Empty => Node(item, itemValue, Empty, Empty)
        case n @ Node(k, _, leftNode, rightNode) =>
          if (item < k) n.copy(left = insert(item, itemValue, leftNode))
          else if (item > k) n.copy(right = insert(item, itemValue, rightNode))
          else n.copy(value = itemValue)
      }
    }
  }
}