Here is another approach, using a nested map of maps as tree representation.
I have documented the code to make it hopefully easy to understand. 
defmodule DepthFirstTree do
def main(list \\ ["/2/3", "/2/4", "/2/4/6", "/2/3/7", "/2/3/5", "/2/3/8"]) do
list
|> build_tree
|> traverse_depth_first
end
@doc """
Transforms a list of paths into a nested map of maps, by splitting the paths on `/`.
"""
def build_tree(paths) do
paths
|> Enum.map(&path_to_tree/1)
|> Enum.reduce(%{}, &deep_merge/2)
end
@doc """
Turns a path like "a/b/c" into a nested map of maps like %{"a" => %{"b" => %{"c" => %{}}}}
"""
def path_to_tree(path) do
path
|> String.split("/")
|> Enum.reverse
|> Enum.reduce(%{}, fn segment, inner_tree -> %{segment => inner_tree} end)
end
@doc """
Combines two nested map of maps.
"""
def deep_merge(map1, map2) do
Map.merge(map1, map2, fn _, val1 = %{}, val2 = %{} ->
deep_merge(val1, val2)
end)
end
@doc """
Does a depth-first traversal over a nested map of maps, in sorted-key order.
First visits the current node, then its lowest child subtree, then the second-lowest subtree, ... then the highest subtree.
This implementation is not tail-recursive; more performant alternatives (that might be less readable) probably exist.
"""
def traverse_depth_first(prefix \\ nil, tree) do
tree
|> Enum.sort
|> Enum.flat_map(fn
{key, subtree} ->
full_prefix = reconstruct_path(prefix, key)
[full_prefix | traverse_depth_first(full_prefix, subtree)]
end)
end
@doc """
Helper function to combine a prefix and a key back to a path.
"""
def reconstruct_path(prefix, key) do
if prefix == nil do
key
else
prefix <> "/" <> key
end
end
end
