binary_search_tree.exs

# Binary search tree

defmodule Leaf do
  @type t :: %__MODULE__{
    value: integer,
    left: t | nil,
    right: t | nil
  }
  defstruct [:left, :right, :value]

  @spec find(leaf :: t, value :: integer) :: t | nil
  def find(nil, _value), do: nil
  def find(leaf, value) do
    cond do
      leaf.value == value -> leaf
      leaf.value > value -> find(leaf.left, value)
      leaf.value < value -> find(leaf.right, value)
    end
  end

  @spec insert(leaf :: t, value :: integer) :: t
  def insert(nil, value), do: %Leaf{value: value}
  def insert(leaf, value), do: insert_leaf(leaf, %Leaf{value: value})

  defp insert_leaf(nil, new_leaf), do: new_leaf
  defp insert_leaf(leaf, new_leaf) do
    cond do
      leaf.value == new_leaf.value -> leaf

      leaf.value > new_leaf.value ->
        left_leaf = insert_leaf(leaf.left, new_leaf)
        %Leaf{leaf | left: left_leaf}

      leaf.value < new_leaf.value ->
        right_leaf = insert_leaf(leaf.right, new_leaf)
        %Leaf{leaf | right: right_leaf}
    end
  end

  @spec delete(leaf :: t, value :: integer) :: t
  def delete(nil, _value), do: nil
  def delete(leaf, value) do
    cond do
      leaf.value == value -> splice(leaf)

      leaf.value > value ->
        left_leaf = delete(leaf.left, value)
        %Leaf{leaf | left: left_leaf}

      leaf.value < value ->
        right_leaf = delete(leaf.right, value)
        %Leaf{leaf | right: right_leaf}
    end
  end

  # Remove this leaf and splice any child leaves back together.
  defp splice(leaf), do: splice(leaf.left, leaf.right)
  defp splice(left, nil), do: left
  defp splice(nil, right), do: right
  defp splice(left, right), do: insert_leaf(right, left)
end

defmodule Tree do
  #       9
  #   4       20
  # 1   6   15   170
  def new do
    %Leaf{
      value: 9,
      left: %Leaf{
        value: 4,
        left: %Leaf{value: 1},
        right: %Leaf{value: 6}
      },
      right: %Leaf{
        value: 20,
        left: %Leaf{value: 15},
        right: %Leaf{value: 170}
      }
    }
  end
end

defimpl Inspect, for: Leaf do
  def inspect(leaf, _opts), do: do_inspect(leaf, 0) |> String.trim_trailing

  defp do_inspect(leaf, level) do
    padding =
      (0..level)
      |> Enum.reduce("", fn padding_level, acc ->
        case padding_level do
          0 -> ""
          _ -> "  " <> acc
        end
      end)

    padding <> "value: #{leaf.value}\n" <>
    case leaf.left do
      nil -> ""
      left -> padding <> "left:\n#{do_inspect(left, level + 1)}"
    end <>
    case leaf.right do
      nil -> ""
      right -> padding <> "right:\n#{do_inspect(right, level + 1)}"
    end
  end
end

tree = Tree.new

found = Leaf.find(tree, 15)
IO.puts "found 15:\n#{inspect found}\n"

found = Leaf.find(tree, 6)
IO.puts "found 6:\n#{inspect found}\n"

not_found = Leaf.find(tree, 5)
IO.puts "found 5:\n#{inspect not_found}\n"

insert = Leaf.insert(tree, 130)
IO.puts "insert 130:\n#{inspect insert}\n"

insert = Leaf.insert(tree, 180)
IO.puts "insert 180:\n#{inspect insert}\n"

insert = Leaf.insert(tree, 4)
IO.puts "insert 4:\n#{inspect insert}\n"

delete = Leaf.delete(tree, 15)
IO.puts "delete 15:\n#{inspect delete}\n"

delete = Leaf.delete(tree, 20)
IO.puts "delete 20:\n#{inspect delete}\n"

delete = Leaf.delete(tree, 9)
IO.puts "delete 9:\n#{inspect delete}\n"