tree structure in ruby with parent child in array format without gems?

arrays, ruby, ruby-on-rails

Solution

This is easier than you think, you just need to realize a couple simple things:

- `nil` is a perfectly valid Hash key.

- You can use `nil` as a virtual root for your tree so that all the `:parent_id`s point at things in your tree.

- You can iterate through the array and track entries in two ways at once: by `:id` and by `:parent_id`.

First a tree represented by a Hash:

tree = Hash.new { |h,k| h[k] = { :title => nil, :children => [ ] } }

We're going to be going from the root to the leaves so we're only interested in the children side of the parent/child relationship, hence the `:children` array in the default values.

Then a simple iteration that fills in the `:title`s and `:children` as it goes:

arr.each do |n|
  id, parent_id = n.values_at(:id, :parent_id)
  tree[id][:title] = n[:title]
  tree[parent_id][:children].push(tree[id])
end

Note that the nodes (including the parent nodes) are automatically created by `tree`'s `default_proc` the first time they're seen so the node order in `arr` is irrelevant.

That leaves us with the tree in `tree` where the keys are `:id`s (including the virtual root at the `nil` key) and the values are subtrees from that point.

Then if you look at `tree[nil][:children]` to peel off the virtual root, you'll see this:

[
  { :title => "A", :children => [
    { :title => "A1", :children => [
      { :title => "A11", :children => [] },
      { :title => "12", :children => [
        { :title => "A2=121", :children => [] }  
      ] }
    ] },
    { :title => "A2", :children => [
      { :title => "A21", :children => [] }   
    ] }
  ] },
  { :title => "B", :children => [
    { :title => "B11", :children => [] },
    { :title => "B12", :children => [] }
  ] }
]

and that has exactly the structure you're looking for and you should be able to take it from there. That doesn't match your sample response but that's because your sample `arr` doesn't either.

You could also say:

tree = arr.each_with_object(Hash.new { |h,k| h[k] = { :title => nil, :children => [ ] } }) do |n, tree|
  #...
end

if you preferred that rather noisy first line to a separate `tree` declaration.

Problem

I have a array which have list of item like this ``` arr = [ {:id=>1, :title=>"A", :parent_id=>nil}, {:id=>2, :title=>"B", :parent_id=>nil}, {:id=>3, :title=>"A1", :parent_id=>1}, {:id=>4, :title=>"A2", :parent_id=>1}, {:id=>5, :title=>"A11", :parent_id=>3}, {:id=>6, :title=>"12", :parent_id=>3}, {:id=>7, :title=>"A2=121", :parent_id=>6}, {:id=>8, :title=>"A21", :parent_id=>4}, {:id=>9, :title=>"B11", :parent_id=>2}, {:id=>10, :title=>"B12", :parent_id=>2}, ``` ... ] If parent_id is nil then its should be the parent node, if parent_id is not nil then it should comes under the particular parent. Based on id and parent_id, I want to provide a response like this: ``` -A -A1 -A11 -A12 -A123 -A2 -A21 -B -B1 -B11 -B12 ``` How could I generate a responds mentioned above?

Original source