How to sort a hierarchical array of hashes

Question

I'm working with an array like the below:

arr = [{
            item: "Subject",
            id: "16",
            parent_id: ""
         },
         {
            item: "Math",
            id: "17",
            parent_id: "16"
         },
         {
            item: "Geology",
            id: "988",
            parent_id: "208"
         },
         {
            item: "Biology",
            id: "844",
            parent_id: "208"
         },
         {
            item: "Botany",
            id: "594",
            parent_id: "844"
         },
         {
            item: "Science",
            id: "208",
            parent_id: "16"
         }
]

I'm wanting to sort them so and print them out so that they display like this, grouping them and showing their parentage within the hierarchy as indentations:

Subject
   Math
   Science
      Geology
      Biology
        Botany

I'm fairly stumped on how to accomplish this. I am ultimately wanting to iterate through the array only once, but I get stuck when I realize that a parent item may come after its child. Any help is greatly appreciated.

Edit: eliminated the duplicate item

Answer 1

To sort an array by an attribute of its elements...

arr = arr.sort_by{ |e| e[:parent_id] }

Then a little recursion to walk the tree...

def display_hierarchy(arr, parent_id="", level = 0)
  current_indent = 2 * level
  arr.select{ |e| e[:parent_id] == parent_id }.each do |elem|
    name = elem[:item]
    puts name.rjust(name.length + current_indent)
    display_hierarchy(arr, elem[:id], level + 1)
  end
end

Putting it all together...

arr = arr.sort_by{ |e| e[:parent_id] }
display_hierarchy(arr)

Note, if you have duplicate parents, you will get duplicate branches (hint: your example array has a duplicate "Science" node).

Also note, sorting the array ahead of time doesn't really matter for the tree, since it is a hierarchy, I just added it to show how to do it. You'd probably just sort each set of children like so...

def display_hierarchy(arr, parent_id="", level = 0)
  current_indent = 2 * level
  arr.select{ |e| e[:parent_id] == parent_id }.sort_by{ |e| e[:item]}.each do |elem|
    name = elem[:item]
    puts name.rjust(name.length + current_indent)
    display_hierarchy(arr, elem[:id], level + 1)
  end
end

And you get this...

Subject
  Math
  Science
    Biology
      Botany
    Geology
  Science
    Biology
      Botany
    Geology

Answer 2

I am ultimately wanting to iterate through the array only once

In a way, you can do that: by transforming the array into a different structure that's more fit for the task. You'd still have to traverse the resulting collection again though.

Say, you could partition the array into groups by their :parent_id:

children = arr.group_by { |subject| subject[:parent_id] }

Then it's your typical recursive walk, where indentation is added on every level:

hierarchical_print = proc do |node, indent = ""|
  puts(indent + node[:item])          # base
  new_indent = indent + "  "
  children[node[:id]]&.each do |child| # recursion
    hierarchical_print.(child, new_indent)
  end
end

Notice the use of &. (the "lonely operator") in there that only calls the method if the callee isn't nil. Because getting a value from a hash with a key that isn't there returns nil.

In your case the root is a node with an empty parent id, so it's readily available from the children hash as well:

hierarchical_print.(children[""].first)

Subject
  Math
  Science
    Geology
    Biology
      Botany
  Science
    Geology
    Biology
      Botany

...well, yes, you do have two Sciences in there.