Convert a single level JSON adjacency list to nested JSON tree

Question

I have a single level, adjacency list that I build from a relational database into a JSON object in a Rails 4 project. It looks like

{
    "6": {
        "children": [
            8,
            10,
            11
        ]
    },
    "8": {
        "children": [
            9,
            23,
            24
        ]
    },
    "9": {
        "children": [
            7
        ]
    },
    "10": {
        "children": [
            12,
            14
        ]
    ...
}

Now I want to get this into a JSON structure to be consumed by jsTree, that looks like

{
   id: "6",
   children: [
            { id: "8", children: [ { id: "9", children: [{id: "7"}] }]
            { id: "10", children: [ { id: "12",...} {id: "14",...} ] }
 ...and so on
}

The problem I am facing with building this kind of a tree is with the issue of backtracking over the nested levels of JSON. The examples in algorithms text books are not enough to match up with my experience where the backtracking issue is simply handled by pushing some elemental data like a number or string to a stack.

Any help with a practical approach to build such a tree is appreciated.

Why not use a gem that adds hierarchical structure to an AR model like acts_as_tree or ancestry or awesome_nested_set? — Mark Thomas
– Mark Thomas, Commented Apr 15, 2014 at 12:57
@MarkThomas yes as much it would have been made my life easier, I'm working on an application that's already been developed on these lines. — anomit
– anomit, Commented Apr 16, 2014 at 10:39

Daniël Knippers · Accepted Answer · 2014-04-15 12:45:08Z

Assuming there is a single root element (since it's a tree) you can use a very short recursive method to build the tree:

def process(id, src)
  hash = src[id]
  return { id: id } if hash.nil? 
  children = hash['children']
  { id: id, children: children.map { |child_id| process(child_id.to_s, src) } }
end

# the 'list' argument is the hash you posted, '6' is the key of the root node
json = process('6', list)

# json value:
#
# {:id=>"6", :children=>[
#   {:id=>"8", :children=>[
#     {:id=>"9", :children=>[
#       {:id=>"7"}]}, 
#     {:id=>"23"}, 
#     {:id=>"24"}]}, 
#   {:id=>"10", :children=>[
#     {:id=>"12"}, 
#     {:id=>"14"}]}, 
#   {:id=>"11"}]}

I added the return { id: id } if hash.nil? line since your input hash did not contain entries for children 7, 11, 12, 14, 23, 24. If their entries would be like below, you can remove that line.

"7" => { "children" => [] },
"11" => { "children" => [] },
"12" => { "children" => [] },
"14" => { "children" => [] },
"23" => { "children" => [] },
"24" => { "children" => [] }

In that case, the method would yield {:id=>"7", :children=>[]} instead of {:id=>"7"} which you can change if you wish by including a children.empty? check and in that case return a hash with only an :id key (like I do at the hash.nil? check). However, in terms of consistency I would probably favor having the children key present with an empty Array as value, rather than omitting it entirely.

Collectives™ on Stack Overflow

Convert a single level JSON adjacency list to nested JSON tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related