Algorithm for parsing a flat tree into a non-flat tree

I have the following flat tree:

id    name                        parent_id    is_directory
===========================================================
50    app                         0            1
31    controllers                 50           1
11    application_controller.rb   31           0
46    models                      50           1
12    test_controller.rb          31           0
31    test.rb                     46           0

and I am trying to figure out an algorithm for getting this into the following tree structuree:

[{
  id: 50,
  name: app,
  is_directory: true
  children: [{
    id: 31,
    name: controllers,
    is_directory: true,
    children: [{
      id: 11,
      name: application_controller.rb
      is_directory: false
    },{
      id: 12,
      name: test_controller.rb,
      is_directory: false
    }],
  },{
    id: 46,
    name: models,
    is_directory: true,
    children: [{
      id: 31,
      name: test.r开发者_高级运维b,
      is_directory: false
    }]
  }]
}]

Can someone point me in the right direction? I'm looking for steps (eg. build an associative array; loop through the array looking for x; etc.).

I'm using Ruby, so I have object-oriented language features at my disposal.

In ruby, you should be able to easily do it in linear time O(n) with a Hash.

# Put all your nodes into a Hash keyed by id  This assumes your objects are already Hashes
object_hash = nodes.index_by {|node| node[:id]}
object_hash[0] = {:root => true}

# loop through each node, assigning them to their parents
object_hash.each_value {|node|
  continue if node[:root]
  children = object_hash[node[:parent_id]][:children] ||= []
  children << node
}

#then your should have the structure you want and you can ignore 'object_hash' variable
tree = object_hash[0]

I had investigate the issue, with recursive and non recursive. I put here 2 variants:
"parend_id" = "head_id" # for those examples

Recursivly:

require 'pp'

nodes = [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil},
         {"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1"},
         {"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2"}]

def to_tree(nodes, head_id = nil)
  with_head, without_head = nodes.partition { |n| n['head_id'] == head_id }
  with_head.map do |node|
    node.merge('children' => to_tree(without_head, node['id']))
  end
end

pp to_tree(nodes)

Pros:

• as it should be

Cons!:

• Ruby will fail if we will have >= 3000 nodes (this happen because ruby has stack limitation for points (functions) when ruby need retuns back) If you have 'pp' for the output it will fails on >= 200 nodes

Non recursevly, with cycle:

require 'pp'

nodes = [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil},
         {"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1"},
         {"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2"}]

def to_tree(data)
  data.each do |item|
    item['children'] = data.select { |_item| _item['head_id'] == item['id'] }
  end
  data.select { |item| item['head_id'] == nil }
end

pp to_tree(nodes)

Pros:

• more ruby style

Cons:

• we modifies self object, that is not enough good.

The result of the both ways is:

[{"id"=>"1",
  "name"=>"User №1 Pupkin1",
  "head_id"=>nil,
  "children"=>
   [{"id"=>"2",
     "name"=>"User №2 Pupkin2",
     "head_id"=>"1",
     "children"=>
      [{"id"=>"3",
        "name"=>"User №3 Pupkin3",
        "head_id"=>"2",
        "children"=>[]}]}]}]

Resume

For production it is better to use second way, probably there's a more optimal way to realize it.
Hope written will be useful

1. Build a stack and populate it with the root element.
2. While (there are elements in the stack):
3. Pop an element off the stack and add it to where it belongs in the tree.
4. Find all children of this element in your array and push them into the stack.

To add element to the tree (step 3), you 'd need to find their parent first. A tree data structure should allow you to do that pretty quickly, or you can use a dictionary that contains tree nodes indexed by id.

If you mention which language you 're using a more specific solution could be suggested.

Here are a few changes I had to make to @daniel-beardsley's response to make it work for me.

1) Since I was starting with an activeRecord relation, I started by doing a "as_json"to convert to a hash. Note that all the keys were therefore strings, not symbols.

2) in my case items without parents had a parent value of nil not 0.

3) I got a compile error on the "continue" expression, so I changed that to "next" (can someone explain this to me -- maybe it was a typo by @daniel-beardsley when converting to ruby?)

4) I was getting some crashes for items with deleted parents. I added code to ignore these -- you could also put at the root if you prefer

object_hash = myActiveRecordRelation.as_json.index_by {|node| node["id"]}
object_hash[nil] = {:root => true}

object_hash.each_value {|node|
  next if node[:root]
  next if  node["parent_id"] &&  !object_hash[node["parent_id"]] # throw away orphans

  children = object_hash[node["parent_id"]][:children] ||= []
  children << node
}

tree = object_hash[nil]