Main.elm

type Tree
    = Node Tree Int Tree
    | Nil


leaf : Int -> Tree
leaf v =
    Node Nil v Nil


search : Int -> Tree -> Bool
search v tree =
    case tree of
        Node left currentV right ->
            if v == currentV then
                True

            else
                search v left || search v right

        Nil ->
            False


insert : Int -> Tree -> Tree
insert v tree =
    case tree of
        Node left currentV right ->
            if v < currentV then
                Node (insert v left) currentV right

            else
                Node left currentV (insert v right)

        Nil ->
            leaf v


findMax : Tree -> ( Tree, Int )
findMax tree =
    case tree of
        Node left v Nil ->
            ( left, v )

        Node _ _ right ->
            findMax right

        Nil ->
            ( Nil, -1 )


replaceLeft : Int -> Tree -> Tree -> Tree
replaceLeft v maxLeftTree tree =
    case tree of
        Node left currentV right ->
            if v == currentV then
                maxLeftTree

            else
                Node
                    left
                    currentV
                    (replaceLeft v maxLeftTree right)

        Nil ->
            Nil


delete : Int -> Tree -> Tree
delete v tree =
    let
        delete_ t =
            case t of
                Node Nil lv Nil ->
                    -- 末端だった場合
                    if v == lv then
                        Nil

                    else
                        t

                _ ->
                    delete v t
    in
    case tree of
        Node left currentV Nil ->
            -- 削除ノードの子が左だけだった場合
            if v == currentV then
                left

            else
                Node (delete_ left) currentV Nil

        Node Nil currentV right ->
            -- 削除ノードの子が右だけだった場合
            if v == currentV then
                right

            else
                Node Nil currentV (delete_ right)

        Node left currentV right ->
            if v == currentV then
                let
                    ( maxLeftTree, maxV ) =
                        findMax left
                in
                Node (replaceLeft maxV maxLeftTree left) maxV right

            else if v < currentV then
                Node (delete_ left) currentV right

            else
                Node (delete_ left) currentV (delete_ right)

        Nil ->
            Nil

Main.scala

sealed trait Tree

case class Node(left: Tree, v: Int, right: Tree) extends Tree

case object Empty extends Tree

object Hello extends App {

  def delete(v: Int, tree: Tree): Tree = {
    def delete_(t: Tree): Tree =
      t match {
        case Node(Empty, lv, Empty) =>
          if(v == lv)
            Empty
          else
            t
         case _ =>
            delete(v, t)
      }

    tree match {
      case Node(left, currentV, Empty) =>
        if(v == currentV)
          left
        else
          Node(delete_(left), currentV, Empty)
      case Node(Empty, currentV, right) =>
        if(v == currentV)
          right
        else
          Node(Empty, currentV, delete_(right))
      case Node(left, currentV, right) =>
        if(v == currentV) {
          val (maxLeftTree, maxV) = findMax(left)
          Node(replaceLeft(maxV, maxLeftTree, left), maxV, right)
        } else if(v < currentV)
          Node(delete_(left), currentV, right)
        else
          Node(delete_(left), currentV, delete_(right))
      case Empty =>
        Empty
        }
    }
  
  private def findMax(tree: Tree): (Tree, Int) =
    tree match {
      case Node(left, v, Empty) =>
        (left, v)
      case Node(_, _, right) =>
        findMax(right)
      case Empty =>
        (Empty, -1)
    }

  private def replaceLeft(v: Int, maxLeftTree: Tree, tree: Tree): Tree =
    tree match {
      case Node(left, currentV, right) =>
        if(v == currentV)
          maxLeftTree
        else 
          Node(left, currentV, replaceLeft(v, maxLeftTree, right))
      case Empty =>
        Empty
    }
}

Tests.elm

tree =
    Node
        (Node (leaf 1) 3 (Node (leaf 4) 6 (leaf 7)))
        8
        (Node Nil 10 (Node (leaf 13) 14 Nil))


searchTest : Test
searchTest =
    describe "search" <|
        [ test "1はtreeに含まれる" <|
            \() ->
                tree
                    |> search 1
                    |> Expect.equal True
        , test "5はtreeに含まれない" <|
            \() ->
                tree
                    |> search 5
                    |> Expect.equal False
        , test "14はtreeに含まれる" <|
            \() ->
                tree
                    |> search 14
                    |> Expect.equal True
        ]


insertTest : Test
insertTest =
    describe "insert" <|
        [ test "2は、左側の1の右に入る" <|
            \() ->
                tree
                    |> insert 2
                    |> Expect.equal
                        (Node
                            (Node (Node Nil 1 (leaf 2)) 3 (Node (leaf 4) 6 (leaf 7)))
                            8
                            (Node Nil 10 (Node (leaf 13) 14 Nil))
                        )
        , test "9は、右側の10の左に入る" <|
            \() ->
                tree
                    |> insert 9
                    |> Expect.equal
                        (Node
                            (Node (leaf 1) 3 (Node (leaf 4) 6 (leaf 7)))
                            8
                            (Node (leaf 9) 10 (Node (leaf 13) 14 Nil))
                        )
        ]


deleteTest : Test
deleteTest =
    describe "delete" <|
        [ test "末端の1はそのまま削除される" <|
            \() ->
                tree
                    |> delete 1
                    |> Expect.equal
                        (Node
                            (Node Nil 3 (Node (leaf 4) 6 (leaf 7)))
                            8
                            (Node Nil 10 (Node (leaf 13) 14 Nil))
                        )
        , test "末端の7はそのまま削除される" <|
            \() ->
                tree
                    |> delete 7
                    |> Expect.equal
                        (Node
                            (Node (leaf 1) 3 (Node (leaf 4) 6 Nil))
                            8
                            (Node Nil 10 (Node (leaf 13) 14 Nil))
                        )
        , test "14を削除した場合、唯一の子13と入れ替わる" <|
            \() ->
                tree
                    |> delete 14
                    |> Expect.equal
                        (Node
                            (Node (leaf 1) 3 (Node (leaf 4) 6 (leaf 7)))
                            8
                            (Node Nil 10 (leaf 13))
                        )
        , test "10を削除した場合、唯一の子14と入れ替わる" <|
            \() ->
                tree
                    |> delete 10
                    |> Expect.equal
                        (Node
                            (Node (leaf 1) 3 (Node (leaf 4) 6 (leaf 7)))
                            8
                            (Node (leaf 13) 14 Nil)
                        )
        , test "3を削除した場合、左の子の最大値である1と入れ替わる" <|
            \() ->
                tree
                    |> delete 3
                    |> Expect.equal
                        (Node
                            (Node Nil 1 (Node (leaf 4) 6 (leaf 7)))
                            8
                            (Node Nil 10 (Node (leaf 13) 14 Nil))
                        )
        , test "8を削除した場合、左の子の最大値である7と入れ替わる" <|
            \() ->
                tree
                    |> delete 8
                    |> Expect.equal
                        (Node
                            (Node (leaf 1) 3 (Node (leaf 4) 6 Nil))
                            7
                            (Node Nil 10 (Node (leaf 13) 14 Nil))
                        )
        ]