n4thyra

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

8 comments

#recursion #structs #trees

0 3031 8

2022-03-23 19:47:34 UTC

Most Liked

stefanchrobot

You could use digraph and digraph_utils to do this.

Post #4

kokolegorille

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"}
]

Post #1

stefanchrobot

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.

Post #8