BST.scala

package com.marimon.datastructures

// based on https://gist.github.com/alhuelamo/3f610055167301d4d2f2d32a954d4b18
sealed trait BST[+A] {
  import BST._

  def insert[AA >: A](
    newValue: AA
  )(implicit ordering: Ordering[AA]): BST[AA] = {
    val res =
      this match {
        case Nope =>
          Leaf(newValue)

        case Leaf(current) =>
          if (ordering.lt(newValue, current))
            Branch(current, Leaf(newValue), empty)
          else
            Branch(current, empty, Leaf(newValue))

        case Branch(current, left, right) =>
          if (ordering.lt(newValue, current))
            Branch(current, left.insert(newValue), right)
          else
            Branch(current, left, right.insert(newValue))

      }
    res
  }

  def insertAll[AA >: A](
    otherTree: BST[AA]
  )(implicit ordering: Ordering[AA]): BST[AA] = {
    this match {
      case Nope        => otherTree
      case Leaf(value) => otherTree.insert(value)
      case Branch(value, left, right) =>
        values.foldLeft(otherTree)(_.insert(_))
    }
  }

  def values[AA >: A]: Seq[AA] = {
    this match {
      case Nope        => Seq.empty[AA]
      case Leaf(value) => Seq(value)
      case Branch(value, left, right) =>
        Seq(value) ++: left.values ++: right.values
    }
  }
  def contains[AA >: A](seeked: AA)(implicit ordering: Ordering[AA]): Boolean =
    this match {
      case Nope        => false
      case Leaf(value) => value == seeked
      case Branch(value, left, right) =>
        if (value == seeked) true
        else if (ordering.lt(value, seeked)) right.contains(seeked)
        else left.contains(seeked)
    }

  def delete[AA >: A](seeked: AA)(implicit ordering: Ordering[AA]): BST[AA] =
    this match {
      case Nope            => Nope
      case x @ Leaf(value) => if (seeked == value) Nope else x
      case x @ Branch(value, left, right) =>
        if (!this.contains(seeked)) this
        else {
          if (value == seeked) {
            BST.empty[AA].insertAll(right).insertAll(left)
          } else if (ordering.lt(seeked, value))
            Branch(value, left.delete(seeked), right)
          else
            Branch(value, left, right.delete(seeked))
        }
    }

  def length: Int = this match {
    case Nope                       => 0
    case Leaf(value)                => 1
    case Branch(value, left, right) => 1 + left.length + right.length
  }
}

case object Nope extends BST[Nothing]
case class Leaf[+A](value: A) extends BST[A]
case class Branch[+A](value: A, left: BST[A], right: BST[A]) extends BST[A]

object BST {
  def empty[A]: BST[A] = Nope
  def apply[A: Ordering](values: A*): BST[A] =
    values.foldLeft(empty[A])(_.insert(_))

}