ruby how to generate a tree structure form array?

Question

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?

Thanks

You could use a gem like github.com/stefankroes/ancestry or github.com/mceachen/closure_tree, both can generate a nested hash — Stefan
– Stefan, Commented Sep 16, 2013 at 13:43
thanks for the support, is it possible to generate it without adding any fields in database? — Arivarasan L
– Arivarasan L, Commented Sep 16, 2013 at 13:51
Closure_tree works with a parent_id column, you just have to set up an additional table and run a rake task, see github.com/mceachen/closure_tree#installation — Stefan
– Stefan, Commented Sep 16, 2013 at 13:53

Stefan · Accepted Answer · 2013-09-16 14:26:53Z

You could use a gem like Closure_tree:

hash_tree provides a method for rendering a subtree as an ordered nested hash:
Tag.hash_tree
#=> {a => {b => {c1 => {d1 => {}}, c2 => {d2 => {}}}, b2 => {}}}

Or Ancestry:

Ancestry can arrange an entire subtree into nested hashes for easy navigation after retrieval from the database. TreeNode.arrange could for example return:
{ #<TreeNode id: 100018, name: "Stinky", ancestry: nil>
  => { #<TreeNode id: 100019, name: "Crunchy", ancestry: "100018">
    => { #<TreeNode id: 100020, name: "Squeeky", ancestry: "100018/100019">
      => {}
    }
  }
}

See https://www.ruby-toolbox.com/categories/Active_Record_Nesting for other gems.

Update

If you have to do it in-memory, something like this should work:

nested_hash = Hash[arr.map{|e| [e[:id], e.merge(children: [])]}]
nested_hash.each do |id, item|
  parent = nested_hash[item[:parent_id]]
  parent[:children] << item if parent
end
tree = nested_hash.select { |id, item| item[:parent_id].nil? }.values

require 'pp'
pp tree

Output

[{:id=>1,
  :title=>"A",
  :parent_id=>nil,
  :children=>
   [{:id=>3,
     :title=>"A1",
     :parent_id=>1,
     :children=>
      [{:id=>5, :title=>"A11", :parent_id=>3, :children=>[]},
       {:id=>6,
        :title=>"12",
        :parent_id=>3,
        :children=>
         [{:id=>7, :title=>"A2=121", :parent_id=>6, :children=>[]}]}]},
    {:id=>4,
     :title=>"A2",
     :parent_id=>1,
     :children=>[{:id=>8, :title=>"A21", :parent_id=>4, :children=>[]}]}]},
 {:id=>2,
  :title=>"B",
  :parent_id=>nil,
  :children=>
   [{:id=>9, :title=>"B11", :parent_id=>2, :children=>[]},
    {:id=>10, :title=>"B12", :parent_id=>2, :children=>[]}]}]

both gems are really awesome, can we make it without any database migrations?

konsolebox · Accepted Answer · 2013-09-16 15:48:31Z

One example:

#!/usr/bin/env ruby

root = {:id => 0, :title => '', :parent_id => nil}

arr = 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},
]

map = {}

arr.each do |e|
  map[e[:id]] = e
end

@@tree = {}

arr.each do |e|
  pid = e[:parent_id]
  if pid == nil || !map.has_key?(pid)
    (@@tree[root] ||= []) << e
  else
    (@@tree[map[pid]] ||= []) << e
  end
end

def print_tree(item, level)
  items = @@tree[item]
  unless items == nil
    indent = level > 0 ? sprintf("%#{level * 2}s", " ") : ""
    items.each do |e|
      puts "#{indent}-#{e[:title]}"
      print_tree(e, level + 1)
    end
  end
end

print_tree(root, 0)

Output:

-A
  -A1
    -A11
    -12
      -A2=121
  -A2
    -A21
-B
  -B11
  -B12

Victor Moroz · Accepted Answer · 2013-09-16 14:26:29Z

5

Don't mean to replace proven gems, but depending on your needs you can use something as simple as:

groups = arr.group_by{ |x| x[:parent_id] }
groups.default = []

build_tree = 
  lambda do |parent| 
    [parent[:title], groups[parent[:id]].map(&build_tree)]
    # or
    # { parent[:title] => groups[parent[:id]].map(&build_tree) }
  end

p build_tree[:id => nil][1] # :id => nil is not required, empty hash will work too
# => [["A", [["A1", [["A11", []], ["A12", [["A122", []]]]]], ["A2", [["A21", []]]]]], ["B", [["B11", []], ["B12", []]]]]

answered Sep 16, 2013 at 14:26

Victor Moroz

9,2351 gold badge21 silver badges23 bronze badges

1 Comment

Arivarasan L Over a year ago

thanks for your time, its complicated for me to understand the concept behind build_tree.

Collectives™ on Stack Overflow

ruby how to generate a tree structure form array?

3 Answers 3

Update

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Update

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related