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.

Answer 1

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.