How could this be written using continuation passing style?
I would like to slightly rewrite the problem before making it continuation based because it will make it clearer and avoid duplication:

defmodule BTree do
  defstruct tree: nil
  def new(e), do: %BTree{tree: {e, nil, nil}}

  def insert(%BTree{tree: root}, element) do
    %BTree{tree: do_insert(root, element)}
  end

  defp do_insert(nil, element) do
    {element, nil, nil}
  end

  defp do_insert({e, l, r}, element) when e &gt; element do
    {e, do_insert(l, element), r}
  end

  defp do_insert({e, l, r}, element) when e &lt; element do
    {e, l, do_insert(r, element)}
  end

  defp do_insert({_, _, _} = tuple, _element) do
    tuple
  end
end 

BTree.new(10) |&gt; BTree.insert(5) |&gt; BTree.insert(15) |&gt; IO.inspect


The previous code was generating a BTree for every node. Instead, we simply treat each node as a tuple with three elements (the node item, left and right). When inserting an element, we traverse the tree until we reach nil. We can make it tail recursive by passing a function and invoking the previous one at each step:

defmodule BTree do
  defstruct tree: nil
  def new(e), do: %BTree{tree: {e, nil, nil}}

  def insert(%BTree{tree: root}, element) do
    do_insert(root, element, &amp;%BTree{tree: &amp;1})
  end

  defp do_insert(nil, element, fun) do
    fun.({element, nil, nil})
  end

  defp do_insert({e, l, r}, element, fun) when e &gt; element do
    do_insert(l, element, &amp;fun.({e, &amp;1, r}))
  end

  defp do_insert({e, l, r}, element, fun) when e &lt; element do
    do_insert(r, element, &amp;fun.({e, l, &amp;1}))
  end

  defp do_insert({_, _, _} = tuple, _element, fun) do
    fun.(tuple)
  end
end 

BTree.new(10) |&gt; BTree.insert(5) |&gt; BTree.insert(15) |&gt; IO.inspect


Note though I find this code much harder to understand and I don't think you would get any benefit in practice.