Algorithm for converting hierarchical flat data (w/ ParentID) into sorted flat list w/ indentation levels

Question

I have the following structure: ``` MyClass { guid ID guid ParentID string Name } ``` I'd like to create an array which contains the elements in the order they should be displayed in a hierarchy (e.g. according to their "left" values), as well as a hash which maps the guid to the indentation level. For example: ``` ID Name ParentID ------------------------ 1 Cats 2 2 Animal NULL 3 Tiger 1 4 Book NULL 5 Airplane NULL ``` This would essentially produce the following objects: ``` // Array is an array of all the elements sorted by the way you would see them in a fully expanded tree Array[0] = "Airplane" Array[1] = "Animal" Array[2] = "Cats" Array[3] = "Tiger" Array[4] = "Book" // IndentationLevel is a hash of GUIDs to IndentationLevels. IndentationLevel["1"] = 1 IndentationLevel["2"] = 0 IndentationLevel["3"] = 2 IndentationLevel["4"] = 0 IndentationLevel["5"] = 0 ``` For clarity, this is what the hierarchy looks like: ``` Airplane Animal Cats Tiger Book ``` I'd like to iterate through th…

Accepted Answer

Wonsungi's post helped a lot, however that is for a generic graph rather than a tree. So I modified it quite a bit to create an algorithm designed specifically for a tree:

```
// Data strcutures:
nodeChildren: Dictionary['nodeID'] = List<Children>;
indentLevel: Dictionary['nodeID'] = Integer;
roots: Array of nodes;
sorted: Array of nodes;
nodes: all nodes

// Step #1: Prepare the data structures for building the tree
for each node in nodes
  if node.parentID == NULL
    roots.Append(node);
    indentLevel[node] = 0;
  else
    nodeChildren[node.parentID].append(node);

// Step #2: Add elements to the sorted list
roots.SortByABC();
while roots.IsNotEmpty()
  root = roots.Remove(0);
  rootIndentLevel = indentLevel[root];
  sorted.Append(root);
  children = nodeChildren[root];
  children.SortByABC();
  for each child in children (loop backwards)
    indentLevel[child] = rootIndentLevel + 1
    roots.Prepend(child)
```

Algorithm for converting hierarchical flat data (w/ ParentID) into sorted flat list w/ indentation levels

Solution

Problem