How to find total number of children and number of grand children 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 the 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 a better way? Or an easy way I can get this ChildCount as well as the Hierarchy level.

Total child count example:

Input is Id = 10

total children = 3.

The current approach:

RecursiveMethod(List)
{
    For each through the list and find the count
    Call the RecursiveMethod again
}

Answer 1

Use:

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

Answer 2

My attempt at a generic 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"]);
}

Answer 3

We can use the below method to get the 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 the 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();

Answer 4

Notice the childCount property here. It will recursively count the total children in any level of the tree.

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 => Children?.Sum(c => c.ChildCount + 1) ?? 0;
    public int HierarchyLevel { get; set; }
}