How to loop recursive data type

Question

I reading hierarchical data into a recursive data structure.

public class Items
{
    public string Name { get; set; }
    public List<Items> Children { get; set; }
}

So its similar to a tree. My problem is, I have no idea how I can loop over all elements or find a inner element with a specific Name. Since it can be very complex/deep I can not really work with nested loops since I don't know how deep it will get.

How can I have a loop over all elements in such a structure?

Answer 1

I would do it this way:

class Program
{
    static void Main(string[] args)
    {
        List<Item> items = new List<Item>() { new Item { Name = "Pasta", Children = new List<Item>() { new Item { Name = "Pasta", Children = null } } } };
        List<Item> pastas = GetItemsByName(items, "Pasta");
    }

    private static List<Item> GetItemsByName(List<Item> items, string name)
    {
        List<Item> found = new List<Item>();
        foreach (Item item in items)
        {
            if (item.Name == name)
            {
                found.Add(item);
            }
            if (item.Children != null)
            {
                found.AddRange(GetItemsByName(item.Children, name));
            }
        }
        return found;
    }
}


public class Item
{
    public string Name { get; set; }
    public List<Item> Children { get; set; }
}

Answer 2

void RecursiveMethod(Items items)
{
    if (items.Children != null)
    {
        foreach (Items i in items.Children)
        {
            RecursiveMethod(i);
        }
    }
    if (items.Name == "YourName")
    {
        // Do your stuff..
    }
}

Answer 3

You need some traversal algorithm implementation.
There are several ones, either recursive, or non-recursive. It depends on your particular use-cases, which one to choose.

E.g., a kind of non-recursive, lazy width traversal:

public static class TreeVisitor
{
    public static IEnumerable<TNodeType> WidthTraversal<TNodeType>(TNodeType root, Func<TNodeType, IEnumerable<TNodeType>> getChildNodesFunc)
        where TNodeType : class
    {
        if (root == null)
        {
            throw new ArgumentNullException(nameof(root));
        }

        if (getChildNodesFunc == null)
        {
            throw new ArgumentNullException(nameof(getChildNodesFunc));
        }

        var visited = new HashSet<TNodeType>();
        var queue = new Queue<TNodeType>();

        yield return root;
        visited.Add(root);
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            var parent = queue.Dequeue();
            foreach (var child in getChildNodesFunc(parent))
            {
                if (child == default(TNodeType))
                    continue;

                if (!visited.Contains(child))
                {
                    yield return child;
                    visited.Add(child);
                    queue.Enqueue(child);
                }
            }
        }
    }
}

Usage:

        var rootItem = new Items
        {
            Name = "Root",
            Children = new List<Items>
            {
                new Items { Name = "Child1" },
                new Items { Name = "Child2" },
                // etc
            }
        };

        foreach (var item in TreeVisitor.WidthTraversal(rootItem, _ => _.Children))
        {
            // ...
        }

Answer 4

Since you need solution without recursion, here is one:

public Items FindByName(Items root, string targetName)
{
    var stack = new Stack<Items>();
    stack.Push(root);

    Items node;
    while (true)
    {
        node = stack.Pop();
        if (node == null)
        {
            // not found ..
        }
        if (node.Name == targetName)
        {
            break;
        }
        foreach (var child in node.Children)
        {
            stack.Push(child);
        }
    }
    return node;
}