BinarySearchTree.scala

package com.template

trait BinarySearchTree[+T] {
  def insert[R >: T](element: R)(implicit ord: Ordering[R]): BinarySearchTree[R]
  def isEmpty: Boolean
}

case class Node[+T](value: T, left: BinarySearchTree[T], right: BinarySearchTree[T]) extends BinarySearchTree[T] {
  override def isEmpty: Boolean = false
  override def insert[R >: T](element: R)(implicit ord: Ordering[R]): BinarySearchTree[R] = {
    import ord._
    if (value < element) Node(value, left, insertRight(element, right)) else Node(value, insertLeft(element, left), right)
  }

  private def insertRight[R >: T](element: R, rightTree: BinarySearchTree[R])(implicit ord: Ordering[R]): BinarySearchTree[R] = {
    import ord._
    rightTree match {
      case EmptyTree => Node(element, EmptyTree, EmptyTree)
      case Node(value, left, right) =>
        if (value < element)
          Node(value, left, insertRight(element, right))
        else
          Node(value, insertLeft(element, left), right)
    }
  }

  private def insertLeft[R >: T](element: R, leftTree: BinarySearchTree[R])(implicit ord: Ordering[R]): BinarySearchTree[R] = {
    import ord._
    leftTree match {
      case EmptyTree => Node(element, EmptyTree, EmptyTree)
      case Node(value, left, right) =>
        if (value < element)
          Node(value, left, insertRight(element, right))
        else
          Node(value, insertLeft(element, left), right)
    }
  }

}

case object EmptyTree extends BinarySearchTree[Nothing] {
  override def insert[R >: Nothing](element: R)(implicit ord: Ordering[R]): BinarySearchTree[R] = Node(element, EmptyTree, EmptyTree)

  override def isEmpty: Boolean = true
}

object BST extends App {
  val tree = Node(1, EmptyTree, EmptyTree)
  println(
    tree.insert(2).insert(3).insert(4)
  )

  println(
    EmptyTree.insert(20).insert(10).insert(30)
  )
}