What is the best way to get the level from a tree data structure using LINQ?

Question

I have a collection demonstrates a tree data structure, it's node is:

Node:
Id
Name
ParentID

Now, I want to get the level for each node in this collection, I tried with the following code but I wonder if it's the best way to implement that.

Func<int, int> GetLevel = (nodeID) =>
{
    int _level = 0;
    var _node = source.First(p => p.Id == nodeID);

    // while hasn't reached the root yet
    while (_node .ParentID.HasValue)
    {
        _level++;
        _node = source.First(p => p.Id == _node.ParentID);
    }
    return _level;
};

// source is a collection of Node.

var query =   from node in source
              select new
              {
                  Id = node.Id,
                  Name = node.Name,
                  ParentID = node.ParentID,
                  Level = GetLevel(node.Id)
              };

I think that the overhead in GetLevel function is able to decrease. or maybe there is a better way to get it directly without this function!

Any idea!

Answer 1

With this Node class you can do this easily.

public class Subject
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
    public string Name { get; set; }
}

Create a tree and show the level of each node:

var list = new List<Subject>
{
    new Subject {Id = 0, ParentId = null, Name = "A"},
    new Subject {Id = 1, ParentId = 0, Name = "B"},
    new Subject {Id = 2, ParentId = 1, Name = "C"},
    new Subject {Id = 3, ParentId = 1, Name = "D"},
    new Subject {Id = 4, ParentId = 2, Name = "E"},
    new Subject {Id = 5, ParentId = 3, Name = "F"},
    new Subject {Id = 6, ParentId = 0, Name = "G"},
    new Subject {Id = 7, ParentId = 4, Name = "H"},
    new Subject {Id = 8, ParentId = 3, Name = "I"},
};
var rootNode = Node<Subject>.CreateTree(list, n => n.Id, n => n.ParentId).Single();

foreach (var node in rootNode.All)
{
    Console.WriteLine("Name {0} , Level {1}", node.Value.Name, node.Level);
}

Answer 2

You could do it top-down in n steps with Breadth First Traversal. Your approach is n*log(n)as far as I can see?

A quick hack in LinqPad with a node class with Level field

class Node
{
    public string Id;
    public string ParentID;
    public int Level;
    public Node SetLevel(int i)
    {
        Level = i;
        return this;
    }
}

void Main()
{
    var source = new List<Node>(){
     new Node(){ Id = "1" },
     new Node(){ Id = "2", ParentID="1"},
     new Node(){ Id = "3", ParentID="1"},
     new Node(){ Id = "4", ParentID="2"}
     };

    var queue = source.Where(p => p.ParentID == null).Select(s => s.SetLevel(0)).ToList();
    var cur = 0;

    while (queue.Any())
    {
        var n = queue[0];
        queue.AddRange(source.Where(p => p.ParentID == n.Id).Select(s => s.SetLevel(n.Level + 1)));
        queue.RemoveAt(0);
    }
    source.Dump();
}

Outputs:

Id ParentID Level
 1  null      0
 2    1       1 
 3    1       1
 4    2       2

But this all depends on the complexity of the Linq parts (.Where)