Binary Tree (Unbalanced)

Performance

Operation	Complexity
Find	$O(log(n)$
Delete	$O(log(n)$
Insert	$O(log(n)$

import cats.data.Chain
import cats.Order

sealed trait BinaryTree[+A]
case class Node[+A](l: BinaryTree[A], v: A, r: BinaryTree[A])
  extends BinaryTree[A]
case object Leaf extends BinaryTree[Nothing]

object BinaryTree {

  def insert[A: Order](t: BinaryTree[A], v: A): BinaryTree[A] = t match {
    case Leaf => Node(Leaf, v, Leaf)
    case n @ Node(l, x, r) =>
      if (v < x) Node(insert(l, v), x, r)
      else if (v > x) Node(l, x, insert(r, v))
      else n
  }

  @tailrec
  def rootedAt[A: Order](t: BinaryTree[A], v: A): BinaryTree[A] = t match {
    case Leaf => Leaf
    case n @ Node(l, x, r) =>
      if (v == x) n
      else if (v > x) rootedAt(r, v)
      else rootedAt(l, v)
  }

  def find[A: Order](t: BinaryTree[A], v: A): Option[A] =
    rootedAt(t, v) match {
      case Leaf          => None
      case Node(_, x, _) => Some(x)
    }

  def delete[A: Order](t: BinaryTree[A], v: A): BinaryTree[A] = t match {
    case Leaf =>
    case n @ Node(l, x, r) =>
      if (l == Leaf) r
      else if (r == Leaf) l
      else {
        if (v < x) Node(delete(l, v), x, r)
        else if (v > x) Node(l, x, delete(r, v))
        else deleteRoot(n)
      }
  }

  @tailrec
  def leftistElem[A](t: BinaryTree[A]): Option[A] = t match {
    case Leaf             => None
    case Node(Leaf, x, _) => Some(x)
    case Node(l, _, _)    => leftistElem(l)
  }

  def deleteRoot[A: Order](t: BinaryTree[A]): BinaryTree[A] = t match {
    case Node(Leaf, _, r) => r
    case Node(l, _, Leaf) => l
    case Node(l, _, r) =>
      val le = leftistElem(r).get
      Node(l, le, delete(r, le))
  }

  def successor[A: Order](t: BinaryTree[A], v: A): Option[A] =
    rootedAt(t, v) match {
      case Leaf          => None
      case Node(_, _, r) => leftistElem(r)
    }

  def predecessor[A: Order](t: BinaryTree[A], v: A): Option[A] =
    rootedAt(t, v) match {
      case Leaf => None
      case Node(l, _, _) =>
        @tailrec
        def go(t: BinaryTree[A]): Option[A] = t match {
          case Leaf             => None
          case Node(_, x, Leaf) => Some(x)
          case Node(_, _, r)    => go(r)
        }
        go(l)
    }

  def inorder[A: Order](t: BinaryTree[A]): Chain[A] = t match {
    case Leaf          => Chain.empty
    case Node(l, x, r) => inorder(l) ++ Chain(x) ++ inorder(r)
  }

  def preorder[A: Order](t: BinaryTree[A]): Chain[A] = t match {
    case Leaf          => Chain.empty
    case Node(l, x, r) => Chain(x) ++ preorder(l) ++ preorder(r)

  }

  def postorder[A: Order](t: BinaryTree[A]): Chain[A] = t match {
    case Leaf          => Chain.empty
    case Node(l, x, r) => postorder(l) ++ postorder(r) ++ Chain(x)
  }
}

NOTE: Chain is constant time append and prepend ordered data structure