defmodule Demo do
  def paths(tree) do
    paths(tree, [], [])
  end

  defp paths(tree, parent_path, paths) do
    {_,paths} = Enum.reduce(tree, {parent_path, paths}, &descend/2)
    paths
  end

  defp descend({key, value}, {parent_path, paths}) do
    paths =
    if is_map(value) do
      paths(value, [key|parent_path], paths)
    else
      [:lists.reverse([key|parent_path])|paths]
    end
    {parent_path, paths}
  end

  def run(tree) do
    tree
    |> Demo.paths()
    |> IO.inspect()
  end

end

Demo.run(%{})
Demo.run(%{k11: 11})
Demo.run(%{k1: %{k11: 11}})
Demo.run(%{k1: %{k11: 11}, k2: 2})
Demo.run(%{k1: %{k11: 11}, k2: %{k21: 21} })
Demo.run(%{k1: %{k11: 11}, k2: %{k21: 21, k22: 22}})

$ elixir demo.exs
[]
[[:k11]]
[[:k1, :k11]]
[[:k2], [:k1, :k11]]
[[:k2, :k21], [:k1, :k11]]
[[:k2, :k22], [:k2, :k21], [:k1, :k11]]

defmodule Demo do
  def paths(tree),
    do: paths(Map.to_list(tree), [], [], [])

  defp paths([], _, [], paths),
    do: paths

  defp paths([], _, [{parent, others} | rest], paths),
    do: paths(others, parent, rest, paths)

  defp paths([{key, value} | others], parent, rest, paths) when is_map(value),
    do: paths(Map.to_list(value), [key | parent], [{parent, others} | rest], paths)

  defp paths([{key, _} | others], parent, rest, paths),
    do: paths(others, parent, rest, [:lists.reverse([key | parent]) | paths])

  def run(tree) do
    tree
    |> Demo.paths()
    |> IO.inspect()
  end
end

Demo.run(%{})
Demo.run(%{k1: 1})
Demo.run(%{k1: %{k11: 11}})
Demo.run(%{k1: %{k11: 11}, k2: 2})
Demo.run(%{k1: %{k11: 11}, k2: %{k21: 21}})
Demo.run(%{k1: %{k11: 11}, k2: %{k21: 21, k22: 22}})
Demo.run(%{k1: %{k11: %{k111: 111, k112: 112}, k12: 12}, k2: %{k21: 21, k22: 22}})

$ elixir demo.exs
[]
[[:k1]]
[[:k1, :k11]]
[[:k2], [:k1, :k11]]
[[:k2, :k21], [:k1, :k11]]
[[:k2, :k22], [:k2, :k21], [:k1, :k11]]
[[:k2, :k22], [:k2, :k21], [:k1, :k12], [:k1, :k11, :k112], [:k1, :k11, :k111]]
$

Here’s a compact, non-tail-recursive implementation:

defmodule Nmap do
  def trace_map(map) when is_map(map) do
    # In a simple case the result of this function will be a list of one-element lists. For example,
    #
    #     trace_map(%{k1: 1, k2: 2}) == [[:k1], [:k2]]
    #
    # However, if there are nested maps, the top-level key will be prepended to all subpaths returned from the recursive
    # calls of this function:
    #
    #     trace_map(%{k1: %{k11: 11, k12: 12}, k2: 2}) == [[:k1, :k11], [:k1, :k12], [:k2]]
    #
    # This is why we're using Enum.flat_map for the iteration here: to allow recursive function calls to return a list
    # that will then be spliced into the parent list instead of being added to the parent as a single list of lists. If
    # we were to use just Enum.map, we'd get the following result instead:
    #
    #     trace_map(%{k1: %{k11: 11, k12: 12}, k2: 2}) ==
    #       [
    #         [[:k1, :k11], [:k1, :k12]],  # return value of the first recursive call
    #         [[:k2]]
    #       ]
    #
    Enum.flat_map(map, fn
      {key, nested_map} when is_map(nested_map) ->
        # If the value is a nested map, get its list of paths recursively and prepend the current key to each of them.
        for key_list <- trace_map(nested_map) do
          [key | key_list]
        end

      {key, _val} ->
        # For plain values return the key to end the recursion. The key is wrapped in a list twice because flat_map
        # will unwrap the outermost list and the remainder will be used as a list tail by the calling function (the one
        # immediately up the stack).
        [[key]]
    end)
  end
end

Usage example:

iex(21)> m = %{k1: %{k11: 11, k12: %{k121: 121}, k13: 13}, k2: 2}
%{k1: %{k11: 11, k12: %{k121: 121}, k13: 13}, k2: 2}

iex(22)> paths = Nmap.trace_map(m)
[[:k1, :k11], [:k1, :k12, :k121], [:k1, :k13], [:k2]]

iex(23)> for path <- paths do
...(23)>   get_in(m, path)
...(23)> end
[11, 121, 13, 2]

Thanks, guys! FWIW, I opted to use a slight variation on Peer’s first version:

  def leaf_paths(tree), do: leaf_paths(tree, [], [])

  defp leaf_paths(tree, parent_path, paths) do
    {_, paths} = Enum.reduce(tree, {parent_path, paths}, &descend/2)
    paths
  end

  defp descend({key, value}, {parent_path, paths}) when is_map(value), do:
    {parent_path, leaf_paths(value, [ key | parent_path ], paths) }
    
  defp descend({key, _value}, {parent_path, paths}), do:
    {parent_path, [ :lists.reverse( [ key | parent_path ] ) | paths ] }

-r