binary_tree.exs

defmodule BinaryTree do
  defstruct [:left, :right, :value]

  def invert(%__module__{left: left, right: right} = root) do
    %{root| left: invert(right), right: invert(left)}
  end
  def invert(nil), do: nil

  def equals(nil, nil), do: true
  def equals(%{value: a, left: l1, right: r1}, %{value: a, left: l2, right: r2}) do
    equals(l1, l2) and equals(r1, r2)
  end
  def equals(_a, _b), do: false

  def depth(nil), do: 0
  def depth(%{left: left, right: right}) do
    1 + max(depth(left), depth(right))
  end

  def diameter(root) do
    {d, _} = d2(root)
    d
  end

  def d2(nil), do: {0, 0}
  def d2(%{left: left, right: right}) do
    {ld, ldepth} = d2(left)
    {rd, rdepth} = d2(right)
    cd = ldepth + rdepth
    {cd |> max(ld) |> max(rd), max(ldepth, rdepth) + 1}
  end

  def paths(nil), do: []
  def paths(%{left: nil, right: nil, value: value}), do: [[value]]
  def paths(%{left: left, right: right, value: value}) do
    for path <- paths(left) ++ paths(right), do: [value| path]
  end

  def print_paths(root) do
    paths(root) |> Enum.map(&Enum.join(&1, "->"))
  end

  def test do
    three = %BinaryTree{value: 3}
    one = %BinaryTree{value: 1}
    six = %BinaryTree{value: 6}
    nine = %BinaryTree{value: 9}
    seven = %BinaryTree{value: 7, left: six, right: nine}
    two = %BinaryTree{value: 2, left: one, right: three}
    root = %BinaryTree{value: 4, left: two, right: seven}

    2 = root.left.value
    1 = root.left.left.value

    inverted = invert(root)

    7 = inverted.left.value
    9 = inverted.left.left.value

    true = equals(root, root)

    false = equals(root, inverted)

    3 = depth(root)

    three = %BinaryTree{value: 3}
    five = %BinaryTree{value: 5}
    four = %BinaryTree{value: 4}
    two = %BinaryTree{value: 2, left: four, right: five}
    root = %BinaryTree{value: 1, left: two, right: three}
    3 = diameter(root)

    ["1->2->4", "1->2->5", "1->3"] = print_paths(root)

    :ok
  end
end