title: Efficient ordering of hierarchy data with only parentId
body: <p><strong>Problem</strong></p>
  
  <p>What is the fastest method to order a flat unordered set of nodes such that the parent is always listed before it's children. My current solution uses a queue to iterate the tree in a breadth first manner. However I've been wondering if there was a better / more efficient method.</p>
  
  <p>Notes:   </p>
  
  <ul>
  <li>I can't pre compute any values</li>
  <li>Id and ParentId could also be Guids (even if ints I can't guarantee sequential ids)</li>
  </ul>
  
  <p><strong>Linq Pad Code</strong></p>
  
  <pre><code>void Main()
  {
      var nodes = new Node[] {
          new Node { Id = 7, ParentId = 3 },
          new Node { Id = 4, ParentId = 2 },
          new Node { Id = 1, ParentId = 0 },
          new Node { Id = 2, ParentId = 1 },
          new Node { Id = 3, ParentId = 1 },
  
          new Node { Id = 5, ParentId = 2 },
          new Node { Id = 6, ParentId = 3 },
          new Node { Id = 8, ParentId = 0 },
      };
  
      SortHierarchy(nodes).Dump();
  }
  
  IEnumerable&lt;Node&gt; SortHierarchy(IEnumerable&lt;Node&gt; list)
  {
      // hashtable lookup that allows us to grab references to the parent containers, based on id
      var lookup = new Dictionary&lt;int, List&lt;Node&gt;&gt;();
  
      Queue&lt;Node&gt; nodeSet = new Queue&lt;Node&gt;();
      List&lt;Node&gt; children;
  
      foreach (Node item in list) {
          if (item.ParentId == 0) { // has no parent
              nodeSet.Enqueue(item); // This will add all root nodes in the forest
          } else {
              if (lookup.TryGetValue(item.ParentId, out children)) {
                  // add to the parent's child list
                  children.Add(item);
              } else {
                  // no parent added yet
                  lookup.Add(item.ParentId, new List&lt;Node&gt; { item });
              }
          }
      }
  
      while (nodeSet.Any()) {
          var node = nodeSet.Dequeue();
          if (lookup.TryGetValue(node.Id, out children)) {
              foreach (var child in children) {
                  nodeSet.Enqueue(child);
              }
          }
          yield return node;
      }
  }
  
  private class Node {
      public int Id { get; set; }
      public int ParentId { get; set; }
      public string Name { get; set; }
  }
  </code></pre>
  
  <p><strong>Research</strong></p>
  
  <p>I did find this however it wasn't quite what I was after (also the code doesn't work)</p>
  
  <p><a href="https://stackoverflow.com/questions/319108/building-hierarchy-objects-from-flat-list-of-parent-child">Building hierarchy objects from flat list of parent/child</a></p>