Building hierarchy objects from flat list of parent/child

Question

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 modified pre-order tree traversal 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.

For example, given the tree:

• Item A
  • Item A.1
  • Item A.2
    • Item A.2.2
• Item B
  • Item B.1
• Item C

I get the list:

• Item A, Item A.1, Item A.2, Item A.2.2, Item B, Item B.1, Item C

(This is in order of the "left" value from the modified pre-order tree setup).

What I want to do is parse this into objects that contain the actual structure of the tree, eg:

Class TreeObject {
    String Name;
    Guid ID; 
    Guid ParentID;
    List<TreeObject> Children;
}

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:

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

which takes the flat list in, and returns a nested list.

In other words:

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2

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).

---

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.

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.

Monogram

Does this mean your storing the parentId and the left and right values for each node in the db? – Doge

Answer 1

Here's the function I ended up writing. I'm using MPTT to store objects, so the list is in order of the 'left' value, which basically means the parent always comes before any given item in the list. In other words, the item referenced by item.ParentID has always already been added (except in the case of top-level or root nodes).

public class TreeObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
    public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}

public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
    // hashtable lookup that allows us to grab references to containers based on id
    var lookup = new Dictionary<int, TreeObject>();
    // actual nested collection to return
    var nested = new List<TreeObject>();

    foreach (TreeObject item in list)
    {
        if (lookup.ContainsKey(item.ParentId))
        {
            // add to the parent's child list 
            lookup[item.ParentId].Children.Add(item);
        }
        else
        {
            // no parent added yet (or this is the first time)
            nested.Add(item);
        }
        lookup.Add(item.Id, item);
    }

    return nested;
}

and a simple test (that works in LinqPad):

void Main()
{
    var list = new List<TreeObject>() {
        new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
        new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
        new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
        new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
        new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
    };

    FlatToHierarchy(list).Dump();
}

Results:

Since I'm updating this 5 years later, here's a recursive LINQ version:

public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
    return (from i in list 
            where i.ParentId == parentId 
            select new TreeObject {
                Id = i.Id, 
                ParentId = i.ParentId,
                Name = i.Name,
                Children = FlatToHierarchy(list, i.Id)
            }).ToList();
}

Monogram

What's the deal with this line: lookup(item.ParentID).Item(item.ParentID).Add(item); ? Is this a typo? You can only access the item by index at that level, no? – Inpatient

ScottE: No, lookup is a Dictionary, indexed by Guid. This is a bit confusing, but it's because lookup(item.PranteID) contains the PARENT list of item.parentId, or in otherwords, this item's grandparent). so .item(item.parentId) contains the list THIS item is in, and the individual item gets added as a sibling. – Monogram

I'm trying to implement this, but i'm getting lookup is a variable, but is being used like a method, is there something missing, I assume not and I'm just doing something wrong? – Doge

Is this .net? Does it compile? I've added a rework of your code below, that compiles right away, am I doing something wrong? – Doge

Is anyone able to fix this example? – Macrobiotics

Sorry; updated to a working example. The original code way back when I originally asked was in VB and I think the conversion to C# broke it -- and I obviously never tested it, shame on me. Sorry again! – Monogram

What if you have multiple trees within and you want to return all your trees how would you do that? – Bourges

@Bourges I'm not exactly sure what you're asking, but regardless, you should ask it as a new question (and include sample code illustrating the issue). – Monogram

Answer 2

I assume you already know the parent of all items.

All you need to do is to iterate through all item of the list once and add the current item to its parent's children list. Only keep the items without parents in the target nested list.

Here is some pseudo code:

foreach Item item in flatlist
   if item.Parent != null
      Add item to item.Parent.ChildrenList
      Remove item from flatlist
   end if
end for

As for getting the parents, from what I can see in your example, you might need to parse the name and build a stack as you advance in the list.

This problems looks hard but it really isn't. A lot of people see this problem from the wrong angle; you must not try to populate every children list but rather get rid of the children items from the flat list, then it becomes easy.

Relationship

That's the part I'm not getting. I'm guessing there is a nice way to have a stack that contains all the parents, and keep pushing into it as an item is deeper than its parent, or popping the last one out as you go up. What I want to avoid is looping over the list a bunch of times removing items. – Monogram

Once you know every node's parent, you can go through the list once. I updated my answer with some pseudo code. – Relationship

I know the ID of the parent, but I don't have a reference to the parent object itself (without searching through the list, of course). – Monogram

what does your "flat list" look like, that would help tremendously to understand your answer...I can't just guess what you infer that to be or contain. – Airlie

In some languages, C# for example, this will not work as the compiler will throw a hissy-fit at runtime because you've modified the collection it's enumerating. – Exquisite

Answer 3

you should use a database store architecture like nested set

[ https://en.wikipedia.org/wiki/Nested_set_model ]

Ankh

Answer 4

Alternative version that compiles normally, I wasn't sure if there was a problem with the code above.

private List<Page> FlatToHierarchy(List<Page> list) {
      // hashtable lookup that allows us to grab references to the parent containers, based on id
        Dictionary<int, Page> lookup = new Dictionary<int, Page>();
      // actual nested collection to return
      List<Page> nested = new List<Page>();

      foreach(Page item in list) {
        if (lookup.ContainsKey(item.parentId)) {
          // add to the parent's child list 
          lookup[item.parentId].children.Add(item); //add item to parent's childs list
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        } else {
          // no parent added yet (or this is the first time)
          nested.Add(item);     //add item directly to nested list                
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        }
      }
    return nested;
    }

Doge

Answer 5

Here is an example, hope this helps

class Program
{
    static void Main(string[] args)
    {
        TreeObject a  = new TreeObject() { Name = "Item A" };
        a.Children.Add( new TreeObject() { Name = "Item A.1" });
        a.Children.Add( new TreeObject() { Name = "Item A.2" });

        TreeObject b = new TreeObject() { Name = "Item B" };
        b.Children.Add(new TreeObject() { Name = "Item B.1" });
        b.Children.Add(new TreeObject() { Name = "Item B.2" });

        TreeObject c = new TreeObject() { Name = "Item C" };

        List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });

        string list = BuildList(nodes);
        Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C

        List<TreeObject> newlist = new List<TreeObject>();
        TreeObject temp = null;

        foreach (string s in list.Split(','))
        {
            if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
            {
                temp = new TreeObject() { Name = s };
                newlist.Add(temp);
            }
            else
            {
                temp.Children.Add(new TreeObject() { Name = s });
            }                              
        }

        Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
    }

    static string BuildList(List<TreeObject> nodes)
    {
        StringBuilder output = new StringBuilder();
        BuildList(output, nodes);
        return output.Remove(output.Length - 1, 1).ToString();
    }

    static void BuildList(StringBuilder output, List<TreeObject> nodes)
    {
        foreach (var node in nodes)
        {
            output.AppendFormat("{0},", node.Name);
            BuildList(output, node.Children);
        }
    }
}

public class TreeObject
{
    private List<TreeObject> _children = new List<TreeObject>();

    public string Name { get; set; }
    public Guid Id { get; set; }
    public List<TreeObject> Children { get { return _children; } }
}

}

Outshoot

This is almost the opposite of what I want to do. What I want to end up with is the structure in the 'nodes' variable you show on line 15. I start with a List<TreeObject> with ALL objects directly in it, as siblings (eg, no parent/child relationships are present). – Monogram

Answer 6

Correcting the example given by gregmac

IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
    {
        var q = (from i in list
                where i.parent_id == parentId
                select new
                {
                    id = i.id,
                    parent_id = i.parent_id,
                    kks = i.kks,
                    nome = i.nome
                }).ToList();
        return q.Select(x => new TreeObject
            {
                children = FlatToHierarchy(list, x.id)
            }).ToList();
    }

Monmouthshire

did you test this, I like your approach... and would like to try on a flat table myself. – Smoodge