Flat List to structured List via recursion in C#?

Question

I have an existing class :

public class Product
{
 public int Id { get; set; }
 public int ParentId { get; set; }
 public string Info { get; set; }
}

And I also have a given List<Product>:

var Lst = new List<Product>();
Lst.Add(new Product{ Id=1,ParentId=0,Info="a"});
Lst.Add(new Product{ Id=2,ParentId=0,Info="a"});
Lst.Add(new Product{ Id=3,ParentId=0,Info="a"});
Lst.Add(new Product{ Id=60,ParentId=1,Info="a"});
Lst.Add(new Product{ Id=61,ParentId=1,Info="a"});
Lst.Add(new Product{ Id=62,ParentId=61,Info="a"});
Lst.Add(new Product{ Id=72,ParentId=61,Info="a"});
Lst.Add(new Product{ Id=90,ParentId=2,Info="a"});

Visualization :

1
|
+---60
|
+---61
     |
     +---62
     |
     +---72

2
|
+---90

3

As you can see , the List<> is flat. (all items are in the same level within the list. it's just that the id,parentId represents heirarchy)

Now - I need to create structural List<> so each item in List will be inside its parent object :

so I created an additional structure class which will hold this structure :

public class Node
{
 public Product Product { get; set; }
 public List<Node> LstNodes  { get; set; }
}

So now I can do :

List<Node> lstNodes = new List<Node>();

And initially I can add the root ones :

lstNodes=Lst.Where(product=>product.ParentId==0).Select(node=>new Node{Product=node}).ToList();

And now I can start recursion to insert items with their parents.

So Where is the problem ?

Question:

I want to avoid insertion of root elements first ( root is where ParentId=0).

Is there any way of doing this with one recursive method (including roots) ?

Desired result : 3 nodes in lstNodes where each has its children recursively.

you can do this in a declerative style if you pass a dictionary with Id->Node around to link the children to their parents. But in this case I would just do this in an old fashioned `foreach` loop style ;) - btw: the list should be sorted for Id to make this quite easy but it seems to already be — Random Dev, Dec 10 '14 at 08:31

score 4 · Accepted Answer · edited Dec 10 '14 at 09:52

4

Something like this?

List<Node> GetNodes(List<Product> lst, int parentId = 0)
{
    var childProducts = lst.Where(x=>x.ParentId == parentId);
    return childProducts
           .Select(x=> new Node { Product = x, LstNodes = GetNodes(lst, x.Id)}
           .ToList();
}

And purely generic version:

class Node<T>
{
    public T Item { get; set; }
    public List<Node<T>> LstNodes  { get; set; }
}

List<Node<T>> GetNodes<T>(List<T> lst, Func<T, int> idSelector, Func<T, int> parentIdSelector, int parentId = 0)
{
    var childProducts = lst.Where(x=>parentIdSelector(x) == parentId);
    return childProducts
           .Select(x=> new Node<T> { Item = x, LstNodes = GetNodes<T>(lst, idSelector,parentIdSelector, idSelector(x))})
           .ToList();
}

GetNodes(Lst,x=>x.Id,x=>x.ParentId, 0);

edited Dec 10 '14 at 09:52

Royi Namir

144,742
138
468
792

answered Dec 10 '14 at 08:35

Euphoric

12,645
1
30
44

@RoyiNamir Yeah, it is missing the generic parameter. Fixed my code. – Euphoric Dec 10 '14 at 08:58
@RoyiNamir Yeah. Sorry. Didn't really bother running it through VS. – Euphoric Dec 10 '14 at 09:03
@RoyiNamir I went by your requirement to use recursion. Look at 3dGrabber's answer for better solution. I'm not sure if it is possible to make better recursive solution. – Euphoric Dec 11 '14 at 09:01
Yes I know :-) Just thinking to myself if it possible still using recursion but to reduce on(2). – Royi Namir Dec 11 '14 at 09:02

score 1 · Answer 2 · answered Dec 10 '14 at 09:03

You can try this:

    static List<Node> BuildTree(List<Product> lst, int topID) 
    {
        var tree = Enumerable.Empty<Node>().ToList();
        if (lst == null)
        {
            return tree;
        }

        foreach (var product in lst)
        {
            if (product.ParentId == topID)
            {
                Node node = new Node 
                {
                    Product = product,
                    LstNodes = BuildTree(lst.Where(p => p.ParentId == product.Id).ToList(), product.Id)
                };

                tree.Add(node);
            }
        }

        return tree;
    }

And you can call: List<Node> roots = BuildTree(Lst, 0);

score 1 · Answer 3 · edited May 23 '17 at 12:27

The solutions proposed so far work, but iterate over the entire collection once per node.
This makes them O(n²) and not suitable for large collections (databases, ...).
Here is a solution running in linear time:

var products = new List<Product>();
products.Add(...);
...

var nodes          = products.Select(p => new Node { Product = p }).ToList(); // 1
var nodeWithId     = nodes.ToDictionary(n => n.Product.Id);                   // 2
var parentChildren = nodes.Where(n => n.Product.ParentId != 0)
                          .ToLookup(n => nodeWithId[n.Product.ParentId]);     // 3

foreach (var pc in parentChildren)  // 4
{
    var parent   = pc.Key;
    var children = pc.ToList();

    parent.LstNodes = children;
}

Explanation:

Create the nodes from the products.
Create a dictionary that allows us to easily find a Node with a given id
Create a lookup (dictionary with multiple values per key) that gives us the children of a given node.
Iterate over the lookup an associate the children with their parents

Fixed. Forgot about the special case of the root nodes: There is no NodeId 0. — 3dGrabber, Dec 11 '14 at 09:41

Flat List to structured List via recursion in C#?

3 Answers3