all nested descendants Deep nesting

Question

I have Taxons table with all parent child records:

<ActiveRecord::Relation [

#<Spree::Taxon id: 1, parent_id: nil, position: 0, name: "Brands", 
permalink: "brands", taxonomy_id: 1, lft: 1, rgt: 20, 
icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, icon_updated_at: nil, 
description: nil, created_at: "2017-06-14 08:52:19", updated_at: "2017-06-23 06:34:11", 
meta_title: nil, meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 2, parent_id: nil, position: 0, name: "Brand", permalink: "brand", taxonomy_id: 2, lft: 21, rgt: 22, 
icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, icon_updated_at: nil, description: nil, 
created_at: "2017-06-14 08:52:19", updated_at: "2017- 06-14 08:52:22", meta_title: nil, 
meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 3, parent_id: 1, position: 0, name: 
"Bags", permalink: "brands/bags", taxonomy_id: 1, lft: 2, rgt: 3, 
icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, 
icon_updated_at: nil, description: nil, created_at: "2017-06-14 
08:52:19", updated_at: "2017-06-21 05:03:52", meta_title: nil, 
meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 4, parent_id: 1, position: 0, name: "Mugs", permalink: 
"brands/mugs", taxonomy_id: 1, lft: 4, rgt: 5, icon_file_name: nil, 
icon_content_type: nil, icon_file_size: nil, icon_updated_at: nil, 
description: nil, created_at: "2017-06-14 08:52:20", updated_at: "2017-
06-14 08:58:29", meta_title: nil, meta_description: nil, meta_keywords: 
nil, depth: 0>, 

#<Spree::Taxon id: 5, parent_id: 1, position: 0, name: 
"Clothing", permalink: "brands/clothing", taxonomy_id: 1, lft: 6, rgt: 
11, icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, 
icon_updated_at: nil, description: nil, created_at: "2017-06-14 
08:52:20", updated_at: "2017-06-23 06:34:11", meta_title: nil, 
meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 6, parent_id: 5, position: 0, name: "Shirts", permalink: 
"brands/clothing/shirts", taxonomy_id: 1, lft: 7, rgt: 8, 
icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, 
icon_updated_at: nil, description: nil, created_at: "2017-06-14 
08:52:20", updated_at: "2017-06-20 06:10:16", meta_title: nil, 
meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 7, parent_id: 5, position: 0, name: "T-Shirts", permalink: 
"brands/clothing/t-shirts", taxonomy_id: 1, lft: 9, rgt: 10, 
icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, 
icon_updated_at: nil, description: nil, created_at: "2017-06-14 
08:52:20", updated_at: "2017-06-23 06:34:11", meta_title: nil, 
meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 8, parent_id: 1, position: 0, name: "Ruby", permalink: 
"brands/ruby", taxonomy_id: 2, lft: 12, rgt: 13, icon_file_name: nil, 
icon_content_type: nil, icon_file_size: nil, icon_updated_at: nil, 
description: nil, created_at: "2017-06-14 08:52:21", updated_at: "2017-
06-20 06:09:31", meta_title: nil, meta_description: nil, meta_keywords: 
nil, depth: 0>, 

#<Spree::Taxon id: 9, parent_id: 1, position: 0, name: 
"Apache", permalink: "brands/apache", taxonomy_id: 2, lft: 14, rgt: 15, 
icon_file_name: nil, icon_content_type: nil, icon_file_size: nil, 
icon_updated_at: nil, description: nil, created_at: "2017-06-14 
08:52:21", updated_at: "2017-06-23 06:34:11", meta_title: nil, 
meta_description: nil, meta_keywords: nil, depth: 0>, 

#<Spree::Taxon id: 10, parent_id: 1, position: 0, name: "Spree", permalink: 
"brands/spree", taxonomy_id: 2, lft: 16, rgt: 17, icon_file_name: nil, 
icon_content_type: nil, icon_file_size: nil, icon_updated_at: nil, 
description: nil, created_at: "2017-06-14 08:52:21", updated_at: "2017-
06-14 08:58:29", meta_title: nil, meta_description: nil, meta_keywords: 
nil, depth: 0>, ...]> 

I need a tree structure like this:

parent1(first taxon(first record) with all child if it has)
  - child1
  - child2
  - child3
    - child7
    - child9
  - child4
  - child5
parent2(it has no child)
parent3(Not it has child)
  - child7
  - child9

I short I need each individual taxon with its nested child.

I have tried something like:

Taxon.all.each do |i| 
     i.self_and_descendants.each do |j|
       taxon_with_childs << j
     end

But this gives plain array, but I want array with parent child nesting.

I have also tried:

Taxon.each_with_level(Taxon.root.self_and_descendants) do |taxon, level|
    taxon_with_childs << taxon
  end

But this is giving only first record's children and not a deep nesting.

Answer 1

I think it can be done by DFS function

def add_self_and_descendents(x, taxon_with_childs)
  taxon_with_childs << x
  x.descendants.each do |y|
    add_self_and_descendents(y, taxon_with_childs)
  end
end

Taxon.all.each do |i| 
  add_self_and_descendents(i, taxon_with_childs)
end

And it will have long time if the database is bigger and bigger. But there's no other way to do it with short time because database operation functions only use constant values such as Taxon.where(:parent_id => 1 )

Hope this works for you.