When converting from body recursion to tail recursion you essentially are taking responsibility for managing “your own data stack”. In most functional programming languages the head of a list can be added or removed fairly cheaply - making lists excellent stacks.

Furthermore the BEAM performs “last call optimization”. To some, “tail call optimization” may imply recursive calls within the same function. The BEAM doesn’t allocate a new stack frame even when one function’s “tail call” invokes an entirely different function. So mutual recursion can also be optimized.

With a Tree, last call optimization might look like this:

defmodule Tree do
  defstruct value: nil, left: :leaf, right: :leaf

  def new,
    do: :leaf

  def new(value),
    do: %Tree{value: value}

  def insert(tree, value),
    do: insert(tree, value, [])

  defp insert(:leaf, value, ops) do
    insert_ops(new(value), ops)
  end
  defp insert(%Tree{value: value, left: left, right: right} = tree, new_value, ops) do
    cond do
      value < new_value ->
        insert(right, new_value, [{:right, tree} | ops])
      true ->
        insert(left, new_value, [{:left, tree} | ops])
    end
  end

  defp insert_ops(tree, []),
    do: tree
  defp insert_ops(subtree, [{side, tree} | rest]),
    do: insert_ops(Map.put(tree, side, subtree), rest)

  def traverse(tree, acc, fun),
    do: traverse(tree, acc, fun, [])

  defp traverse(:leaf, acc, _fun, []),
    do: acc
  defp traverse(:leaf, acc, fun, [{right,value} | rest]),
    do: traverse(right, fun.(value, acc), fun, rest)
  defp traverse(%Tree{value: value, left: left, right: right}, acc, fun, ops),
    do: traverse(left, acc, fun, [{right, value} | ops])

  def to_list(tree),
    do: :lists.reverse(Tree.traverse(tree, [], &([&1|&2])))

  def from_enum(enum),
    do: Enum.reduce(enum, Tree.new(), &(Tree.insert(&2,&1)))

end

show = fn tree ->
  IO.inspect(tree)
  IO.inspect(Tree.to_list(tree))
end
show_from_enum = fn enum ->
  show.(Tree.from_enum(enum))
end

show.(Tree.new())
show.(Tree.new(1))
show_from_enum.([])
show_from_enum.([1])
show_from_enum.(1..9)
show_from_enum.(9..1)
show_from_enum.([8,4,12,2,6,10,14,1,3,5,7,9,11,13,15])

Allocating a stack frame is likely a highly optimized BEAM level operation and the memory cost related to how much data is captured in the frame. With tail calls you can be very exact what data needs to be captured but there is some overhead (in complexity and reductions) to explicitly managing that captured data. So the tradeoffs will depend a lot on the details of the particular use case.