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

Question

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.rb,
      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.

Answer 1

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.

Answer 2

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]