How to find total number of childs and Number of grand child levels under a hierarchical list parent in C#

Question

I have a tree menu in my project.

The data looks like below

{ParentId = null, Id = 10, Name "a"}, 
{ParentId = null, Id = 33, Name "aa"}, 
{ParentId = 10 , Id = 11, Name "aaa"}, 
{ParentId = 10, Id = 12, Name "aaaa"}, 
{ParentId = 11, Id = 13, Name "aaaaa"}, 
{ParentId = 56 ,Id = 14, Name "aas"}, 
{ParentId = 78 , Id = 15, Name "adss"}, 
{ParentId = 99 , Id = 16, Name "ader"}

I have created a hierarchical list for holding the data

public class NavBarItem
    {
        public int? Id { get; set; }
        public int? ParentId { get; set; }
        public string Name{get;set;}
        public IEnumerable<NavBarItem> Children { get; set; }
        public int ChildCount { get; set; }
        public int HierarchyLevel { get; set; }
    }

And my recursive method will get data from the table and bind it to the Hierarchical List

What I am trying to get here is total number of children/grandchildren for each and every parent.

For example Parent A has child B and Child B has Child C & D, then the total ChildCount of A should be 3 , B should be 2 and C should be 0

Also I wanted to get the Hierarchy Level in each and every parent.

In the above example : Parent A has Child B and B has other child. So for parent A the hierarchyLevel is 2 and for B it should be 1 and for C it should be 0

Example if i am taking the item with Id = 10 , it has Hierarchy two (number of grand child levels )

 {ParentId = 10 , Id = 11, Name "aaa"}, 
  {ParentId = 11, Id = 13, Name "aaaaa"},

Is there any better way , or easy way I can get this ChildCount as well as the Hierarchy level.

Total Child count example :

Input is Id = 10 

total childs = 3.

Current approach :

RecursiveMethod(List)
{
 for each through the list and find the count 
call the RecursiveMethod again 
}

What have you tried so far and which problems did you get with your code? — Pavel Anikhouski, May 15 '20 at 11:11
@PavelAnikhouski I have created another recursive method to get it done. Looking for better options. instead of recursive methods. may be a good syntax ( even if it does the same recursion at high level ) — Arunprasanth K V, May 15 '20 at 11:13
Why not just create a method on `NavBarItem` that returns the child count of that node recursively? — , May 15 '20 at 11:14
@Knoop what do u meant by creating amethod in NavbarItem ? you mean a method which called by constructor of that class ? — Arunprasanth K V, May 15 '20 at 11:16
Well it's a bit unclear what you're actually trying to accomplish so it's hard to give a good answer. But you might be able to do things like this: https://dotnetfiddle.net/G9rbFv. Whether you want to call it from a constructor or somewhere else I have no idea, you've not shared enough to be able to see what's going on and what you want. — , May 15 '20 at 11:25
@Knoop What I am trying to do is like . I want to get the total childs for each and every node. Second one : Need to get the Maximum hierarchy level each parents have . Example if a parent has a child and that child has another child then parent's hierarchy number is 2 and child's hierarchy number 1 and grand child's hierarchy number is 0 — Arunprasanth K V, May 15 '20 at 11:32
related : [Count depth of a hierarchy of classes](https://stackoverflow.com/questions/34819113/count-depth-of-a-hierarchy-of-classes)( _code in question_), [Find the maximum depth of a tree](https://stackoverflow.com/questions/2304505/find-the-maximum-depth-of-a-tree), [How to determine the depth of a C# Expression Tree Iterativly?](https://stackoverflow.com/questions/15709044/how-to-determine-the-depth-of-a-c-sharp-expression-tree-iterativly) — xdtTransform, May 15 '20 at 11:40
Using Recursive code is only way. Linq does not enumerate through a tree structure. — jdweng, May 15 '20 at 12:51
@jdweng got it. Currently i am using stack data structure to figure out the depth of each item. looking for a nice solution to find the total number of items under each node also. — Arunprasanth K V, May 15 '20 at 12:53

JonasH · Answer 1 · 2020-05-18T06:27:31.467

My attempt at a generic solution:

Edit: Added some comments and other refinements to the solution

    /// <summary>
    /// Maps the nodes in a tree
    /// </summary>
    /// <param name="node">The node to process</param>
    /// <param name="level">
    /// the level of the node in the tree,
    /// 0 for the root node,
    /// 1 for children to the root etc.</param>
    /// <param name="childResults"> The result values for each of the children to the node </param>
    /// <returns> the result value for this node</returns>
    public delegate TResult TreeMapper<in T, TResult>(T node, int level, IEnumerable<TResult> childResults);

    /// <summary>
    /// Maps each node in a tree
    /// </summary>
    /// <param name="root">The root object of the tree</param>
    /// <param name="getChildren">Method to return all children of a node in the tree</param>
    /// <param name="map">
    /// Maps an item to some other type
    /// Inputs are:
    /// 1: The node of the tree
    /// 2: The level of the tree, starting with 0 for the root node
    /// 3: The results from each child to the node
    /// Returns: the result for the node
    /// </param>
    public static TResult MapChildren<T, TResult>(
        T root, 
        Func<T, IEnumerable<T>> getChildren,
        TreeMapper<T, TResult> map)
    {
        return RecurseBody(root, 0);

        TResult RecurseBody(T item, int level) 
            => map(item, level, getChildren(item).Select(child => RecurseBody(child, level + 1)));
    }

This can recurse over any kind of object that describes a tree, and compute some kind of value. This can be used to compute various properties of the tree if different mapping methods are used: Compute total number of nodes in a tree:

(t, l, children) => children.Sum(c => c)+1;

Get the maximum level of a tree:

(t, l, children) => children.DefaultIfEmpty(l).Max()

The the method only produces one result for the entire tree. If you want to keep result for each node, you can either update the node itself, or keep a dictionary with node->result mapping

Unit test that computes the level and number of children of each item in the a tree, similarly to your example:

 public class TestItem
    {
        public TestItem(string name, TestItem[] children )
        {
            Children = children;
            Name = name;
        }
        public TestItem(string name) : this(name, new TestItem[0])
        { }
        public string Name { get; }
        public TestItem[] Children { get; }
    }

    [Test]
    public void Test()
    {
        TestItem test = new TestItem("A", new []
        {
            new TestItem("B", new []
            {
                new TestItem("C"),
                new TestItem("D")
            } ),
        } );

        // Compute the number of children to each node in the tree
        var childrenByItem = new Dictionary<string, int>();
        MapChildren<TestItem, int>(test, i => i.Children, 
            (item, level, childResults) => (childrenByItem[item.Name] = childResults.Sum(c => c)) + 1);

        Assert.AreEqual(3, childrenByItem["A"]);
        Assert.AreEqual(2, childrenByItem["B"]);
        Assert.AreEqual(0, childrenByItem["C"]);
        Assert.AreEqual(0, childrenByItem["D"]);

        // Compute the "Hierarchy Level", i.e. maximal distance to a leaf node, for each node
        var levelByItem = new Dictionary<string, int>();
        Tree.MapChildren<TestItem, int>(test, i => i.Children,
            (item, level, childResults) => levelByItem[item.Name] = childResults.DefaultIfEmpty(-1).Max() + 1);

        Assert.AreEqual(2, levelByItem["A"]);
        Assert.AreEqual(1, levelByItem["B"]);
        Assert.AreEqual(0, levelByItem["C"]);
        Assert.AreEqual(0, levelByItem["D"]);
    }

what is this ? i am not getting your point and what is getChildren(self)??? — Arunprasanth K V, May 15 '20 at 14:31
@Arunprasanth K V added some explanations and better examples. — JonasH, May 15 '20 at 15:19
Thanks for the explanation. But seems like the structure of class and your TestItem is different. Can you use the class NavBarItem which is there in the question — Arunprasanth K V, May 18 '20 at 04:14

score 0 · Accepted Answer · answered May 16 '20 at 02:19

We can use the below method to get depth of a hierarchical list

public static IEnumerable<Tuple<int, T>> FindDepthOfTreeNode<T>(T root, Func<T, IEnumerable<T>> children)
        {
            var stack = new Stack<Tuple<int, T>>();

            stack.Push(Tuple.Create(1, root));

            while (stack.Count > 0)
            {
                var node = stack.Pop();

                foreach (var child in children(node.Item2))
                {
                    stack.Push(Tuple.Create(node.Item1 + 1, child));
                }
                yield return node;
            }
        }

and just use it like below

int depth = menuItem.Children == null ? 0 : menuItem.Children
                                .SelectMany(y => FindDepthOfTreeNode(y, xs => xs.Children ??
                                Enumerable.Empty<NavBarItem>()))
                                .Max(xs => xs.Item1);

For getting the total child count in a hierarchical list node we can use below method.

public static int GetChildCountFromTree(this NavBarItem obj)
        {
            var queue = new Queue<NavBarItem>();
            queue.Enqueue(obj); // Note that you can add first object in the queue constructor

            var result = 0;

            while (queue.Any())
            {
                var current = queue.Dequeue();
                result++;
                if (null != current.Children)
                {
                    foreach (NavBarItem inner in current.Children)
                    {
                        queue.Enqueue(inner);
                    }

                    current.Last =  true;
                }
            }

            return result;
        }

and we can use it like below

ourHirarchyNode.GetChildCountFromTree();

score 0 · Answer 3 · answered May 18 '20 at 08:03

Let me know if this works for you:

var lookup = items.ToLookup(x => x.ParentId);

(int children, int level) Recurse(int? parentId)
{
    var r = lookup[parentId].Select(x => Recurse(x.Id)).ToArray();
    return r.Any() ? (r.Sum(x => x.children + 1), r.Max(x => x.level) + 1) : (0, 0);
}

My Recurse method is a local method.

Here's my test code:

void Main()
{
    var items = new[]
    {
        new NavBarItem() {ParentId = null, Id = 10, Name = "a"},
        new NavBarItem() {ParentId = null, Id = 33, Name = "aa"},
        new NavBarItem() {ParentId = 10 , Id = 11, Name = "aaa"},
        new NavBarItem() {ParentId = 10, Id = 12, Name = "aaaa"},
        new NavBarItem() {ParentId = 11, Id = 13, Name = "aaaaa"},
        new NavBarItem() {ParentId = 56 ,Id = 14, Name = "aas"},
        new NavBarItem() {ParentId = 78 , Id = 15, Name = "adss"},
        new NavBarItem() {ParentId = 99 , Id = 16, Name = "ader"},
    };

    var lookup = items.ToLookup(x => x.ParentId);

    (int children, int level) Recurse(int? parentId)
    {
        var r = lookup[parentId].Select(x => Recurse(x.Id)).ToArray();
        return r.Any() ? (r.Sum(x => x.children + 1), r.Max(x => x.level) + 1) : (0, 0);
    }

    var parents = new int?[] { null, 10, 11, 56, 78, 99 };

    Console.WriteLine(
        String.Join(
            Environment.NewLine,
            parents
                .Select(p => new { p, r = Recurse(p) })
                .Select(x => $"{x.p} => {x.r.children}, {x.r.level}")));
}

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

The results I get are:

 => 5, 3
10 => 3, 2
11 => 1, 1
56 => 1, 1
78 => 1, 1
99 => 1, 1

thanks for your support. I will check and let you know, but do we need to get ids of all items in parents var parents = new int?[] { null, 10, 11, 56, 78, 99 }; is there any other option without this ? because i do have more than one parent here with id null. logically its incorrect but this one is an old db structure and we cannot change this at this moment. I think i may have to iterate though all items with parent id null and do the methods u mentioned here — Arunprasanth K V, May 18 '20 at 08:20
@ArunprasanthKV - No, the `var parents = new int?[] { null, 10, 11, 56, 78, 99 };` was just there to demonstrate how you could call the code. You can just call it like `Recurse(null)` or `Recurse(101)`. — Enigmativity, May 18 '20 at 09:25

How to find total number of childs and Number of grand child levels under a hierarchical list parent in C#

3 Answers3