# Build a tree from a flat structure recursively

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

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

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))
``````

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.

You could use `digraph` and `digraph_utils` to do this.

5 Likes

Curious how exactly btw, got a snippet handy?

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

`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

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
end

# Add all edges; if no parent set, add an edge to the fake root.
for %{id: id, parent_id: parent_id} <- input do
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.

2 Likes