Building tree view algorithm

Question

I am looking for the best and the fastest algorithm for creating tree view from records.

I have records in my database like this:

ID|name|parent
1  Foo  0
2  Boo  1
3  Coo  1
4  Goo  2

The structure I want to receive is:

[{
   name: Foo
   children: [
       {
          name: Boo
          children: [
               {
                   name: Goo
                   children: []
               }
          ]
       },
       {
           name: Coo
           children: []
       }
   ]
}]

I've tried to do this recursively but I am afraid my solution is not optimal enough.

Regards

Answer 1

Typically you do this in three steps:

First, sort the list by parent.

Next, create a hash map (dictionary) of these structures, indexed by ID. That is:

class Node
{
    int Id;
    string Name;
    int Parent;
    List<node> Children;
}

(I'm just using a C-like pseudocode. You'll have to translate to whatever language you're using.)

Then, go through the list sequentially. For each node, add it to the dictionary and also add it to the parent node. That is:

for each item in list
    newNode = CreateNewNode(id, name, parent);
    dictionary.Add(id, newNode);
    if (parent != 0)
        dictionary[parent].Children.Add(newNode);

At this point you have a dictionary that contains all of the items at the top level. But the nodes with children also have them populated. You can then output your treeview by traversing the dictionary and only outputting those nodes that have a parent of 0. That is:

// Output initial stuff here
// and then output all top-level nodes
for each node in dictionary
    if (node.Parent == 0)
    {
        outputNode(node, 0);
    }
// Output closing braces here

And outputNode is recursive:

outputNode(Node node, int level)
{
    // here, compute indentation based on level.
    // you'll want to put that indentation before every output line
    writeLine("{");
    writeLine("name:", node.Name);
    writeLine("children: [");
    for each child in children
        outputNode(child, level+1);
    writeLine("]");
    writeLine("}");
}