Build a tree from a flat structure recursively

Questions / Help
, ,
1

There are similar questions such as Build a Tree of Structs but I haven’t found any that would deal with exactly the same issue that I need to solve.

Let’s say we have an (unsorted) set of data that we load from DB

[
  %{id: 2, name: "Child 2", parent_id: nil},
  %{id: 1 ,name: "Child 1", parent_id: nil},
  %{id: 3, name: "GrandChild 1", parent_id: 1},
  %{id: 5, name: "Child 3", parent_id: nil},
  %{id: 6, name: "GrandGrandChild 1", parent_id: 3},
]

Desired result

[
  %{
    id: 2, 
    name: "Child 2",
    children: [],
  }, 
 %{
    id: 1, 
    name: "Child 1",
    children: [
       %{
           id: 3, 
           name: "GrandChild 1",
           children: [
             %{
                 id: 6, 
                 name: "GrandGrandChild 1",
                 children: []
              }, 
           ]
        }, 
    ],
  }, 
 %{
    id: 5, 
    name: "Child 3",
    children: [],
  }, 
]

There can be N levels, not just 3

2

I would start by selecting root nodes, where parent_id is nil. Then use a recursive constructor to build children’s field.

iex> list = [
  %{id: 2, name: "Child 2", parent_id: nil},
  %{id: 1, name: "Child 1", parent_id: nil},
  %{id: 3, name: "GrandChild 1", parent_id: 1},
  %{id: 5, name: "Child 3", parent_id: nil},
  %{id: 6, name: "GrandGrandChild 1", parent_id: 3}
]
iex> new_node = fn node -> %{id: node.id, name: node.name, children: Enum.filter(list, & &1.parent_id == node.id) |> Enum.map(& new_node.(&1))} end
#Function<44.65746770/1 in :erl_eval.expr/5>
iex> Enum.filter(list, & is_nil(&1.parent_id)) |> Enum.map(& new_node.(&1))                                                                        
[
  %{children: [], id: 2, name: "Child 2"},
  %{
    children: [
      %{
        children: [%{children: [], id: 6, name: "GrandGrandChild 1"}],
        id: 3,
        name: "GrandChild 1"
      }
    ],
    id: 1,
    name: "Child 1"
  },
  %{children: [], id: 5, name: "Child 3"}
]
3 Likes
3

Thanks a lot!

It didn’t work inside a module, so I’ve turned your piece of code into this and it is now working like a charm.

  defp g(list, node) do
    %{
      id: node.id,
      children:
        list
          |> Enum.filter(& &1.parent_id == node.id)
          |> Enum.map(& g(list, &1))
    }
  end

 data
    |> Enum.filter(& is_nil(&1.parent_id))
    |> Enum.map(& g(data, &1))
4

It’s because the anonymous function is using list as a closure…

BTW You can optimize by passing a partial list with root nodes removed, as they are not going to be child of anything.

5

You could use digraph and digraph_utils to do this.

5 Likes
6

Curious how exactly btw, got a snippet handy?

7

I’ve googled but haven’t found much, could you show us how to use it?

8

Enum.group_by is a little more efficient than repeatedly scanning the whole list with Enum.filter, and (IMO) is easier to understand:

defmodule GroupThings do
  def run(data) do
    groups = Enum.group_by(data, & &1.parent_id)

    Enum.map(groups[nil], &associate_children(&1, groups))
  end

  defp associate_children(node, groups) do
    children =
      Enum.map(groups[node.id] || [], &associate_children(&1, groups))

    Map.put(node, :children, children)
  end
end

The key here is transforming the input into a map that can answer the question "what are the nodes that have a given parent_id":

%{
  1 => [%{id: 3, name: "GrandChild 1", parent_id: 1}],
  3 => [%{id: 6, name: "GrandGrandChild 1", parent_id: 3}],
  nil => [
    %{id: 2, name: "Child 2", parent_id: nil},
    %{id: 1, name: "Child 1", parent_id: nil},
    %{id: 5, name: "Child 3", parent_id: nil}
  ]
}
2 Likes
9

Here’s how you can do it with :digraph:

input = [
  %{id: 2, name: "Child 2", parent_id: nil},
  %{id: 1 ,name: "Child 1", parent_id: nil},
  %{id: 3, name: "GrandChild 1", parent_id: 1},
  %{id: 5, name: "Child 3", parent_id: nil},
  %{id: 6, name: "GrandGrandChild 1", parent_id: 3},
]

graph = :digraph.new()

fake_root = %{id: 0, name: "Root", parent_id: nil}

# Add vertices + the fake root vertex.
for %{id: id} = node <- [fake_root | input] do
  :digraph.add_vertex(graph, id, Map.delete(node, :parent_id))
end

# Add all edges; if no parent set, add an edge to the fake root.
for %{id: id, parent_id: parent_id} <- input do
  :digraph.add_edge(graph, id, parent_id || fake_root.id)
end

# I needed recursion, so I introduced a module.
defmodule TreeBuilder do
  def build(graph, vertex) do
    children =
      for child <- :digraph.in_neighbours(graph, vertex) do
        build(graph, child)
      end

    {^vertex, label} = :digraph.vertex(graph, vertex)
    
    Map.put(label, :children, children)
  end
end

%{children: children} = TreeBuilder.build(graph, fake_root.id)
# Get rid of the fake root.
children

The idea here is that the input represents the vertices (id and name) and the edges (parent_id). I introduced a fake root node since working with a tree is easier. I first build the graph/tree and then traverse it. Since :digraph is based on ETS, the code does not need to carry the state around.

3 Likes