title: Building hierarchy objects from flat list of parent/child
body: <p>I have a list of items in a hierarchy, and I'm attempting to parse this list out into an actual hierarchy of objects. I'm using <a href="http://www.sitepoint.com/article/hierarchical-data-database/2/" rel="noreferrer">modified pre-order tree traversal</a> to store/iterate through this list, and so what I have is a subset of the tree, including all children, ordered by their "left" value.</p>
  
  <p>For example, given the tree:</p>
  
  <ul>
  <li>Item A
  
  <ul>
  <li>Item A.1</li>
  <li>Item A.2
  
  <ul>
  <li>Item A.2.2</li>
  </ul></li>
  </ul></li>
  <li>Item B
  
  <ul>
  <li>Item B.1</li>
  </ul></li>
  <li>Item C</li>
  </ul>
  
  <p>I get the list:</p>
  
  <ul>
  <li>Item A, Item A.1, Item A.2, Item A.2.2, Item B, Item B.1, Item C</li>
  </ul>
  
  <p>(This is in order of the "left" value from the modified pre-order tree setup).</p>
  
  <p>What I want to do is parse this into objects that contain the actual structure of the tree, eg:</p>
  
  <pre><code>Class TreeObject {
      String Name;
      Guid ID; 
      Guid ParentID;
      List&lt;TreeObject&gt; Children;
  }
  </code></pre>
  
  <p>The flat list is returned as a List of TreeObjects - and each TreeObject has properties for ID, ParentID, Left, and Right. What I'm looking for is a function:</p>
  
  <pre><code>List&lt;TreeObject&gt; FlatToHeirarchy(List&lt;TreeObject&gt; list); 
  </code></pre>
  
  <p>which takes the flat list in, and returns a nested list.</p>
  
  <p>In other words:</p>
  
  <pre><code>List&lt;TreeObject&gt; flatSet = LoadTreeObjectsFromDatabase(); 
  // flatSet.count == 7; flatSet(0).Children == null
  List&lt;TreeObject&gt; nestedSet = FlatToHeirarchy(flatSet);
  // nestedSet.count == 3; nestedSet(0).Children.count == 2
  </code></pre>
  
  <p>I'm at a loss how to do this - keeping track of parents, and being able to deal with a bigger jump (eg, Item A.2.2 -> Item B).</p>
  
  <hr>
  
  <p>Edit: I'm looking for a non-brute-force solution here (eg, not looping several times, moving items into child nodes, until there are only the top-level parents left). I'm guessing there is an elegant method that can loop once, and just place items as needed.</p>
  
  <p>Remember, they are always in a hierarchal order (since I'm using MPTT), so a given item is going to always be a child or sibling of the previous item, or at least share a parent with the previous item. It is never going to come somewhere else in the tree.</p>