How to traverse this tree structure without recursion c#

Question

This code saves loop data in database, but I have performance issues since the data is so big it saves huge number of records, and in this case recursion causes very heavy load to the memory so I need an alternative solution to recursion knowing that this is an n-ary tree.

    private void ProcessLoops(LoopContainer parent, InboundLoop parentLoop)
    {
        foreach (var segment in parent.Segments)
        {
            if (segment is Loop)
            {
                var segmentLoop = segment as Loop;
                var inboundLoop = new InboundLoop()
                {
                    Inbound834RegisterId = RegisterId,
                    InboundSTId = InboundST.InboundSTId,
                    LoopName = segmentLoop.Specification.Name,
                    LoopNumber = segmentLoop.Specification.LoopId,
                    Sequence = _loopSequence++
                };

                if (parentLoop == null)
                {
                    inboundLoop.InboundLoopId = InboundLoopService.Instance.AddInboundLoop(inboundLoop);
                }
                else
                {
                    inboundLoop.ParentLoopId = parentLoop.InboundLoopId;
                    inboundLoop.InboundLoopId = InboundLoopService.Instance.AddInboundLoop(inboundLoop);
                }
                ProcessLoops(segmentLoop, inboundLoop);
            }
        }
    }

Answer 1

I've created a way to flatten item into the order they would be processed recursively, without using recursion. Since this is a generic extension method, it could be used for anything. For example, you could have T be an Action<> so that you can process them whenever you'd like. Here is the extension method:

public static class EnumerableExtensions
{
    public static List<T> ToRecursiveOrderList<T>(this IEnumerable<T> collection, Expression<Func<T, IEnumerable<T>>> childCollection)
    {
        var resultList = new List<T>();
        var currentItems = new Queue<(int Index, T Item, int Depth)>(collection.Select(i => (0, i, 0)));
        var depthItemCounter = 0;
        var previousItemDepth = 0;
        var childProperty = (PropertyInfo)((MemberExpression)childCollection.Body).Member;
        while (currentItems.Count > 0)
        {
            var currentItem = currentItems.Dequeue();
            // Reset counter for number of items at this depth when the depth changes.
            if (currentItem.Depth != previousItemDepth) depthItemCounter = 0;
            var resultIndex = currentItem.Index + depthItemCounter++;
            resultList.Insert(resultIndex, currentItem.Item);

            var childItems = childProperty.GetValue(currentItem.Item) as IEnumerable<T> ?? Enumerable.Empty<T>();
            foreach (var childItem in childItems)
            {
                currentItems.Enqueue((resultIndex + 1, childItem, currentItem.Depth + 1));
            }
            previousItemDepth = currentItem.Depth;
        }

        return resultList;
    }
}

Here is an example of how to use it. A structure like this will be flattened.

• A
• B
• C
  • D
    • E
  • F
  • G
  • H
    • I
• J
  • K
  • L
    • M
• N
• O
  • P
  • Q
    • R
    • S
  • T

internal class Alpha
{
    public string Value { get; set; }
    public Alpha[] Children { get; set; }

    public override string ToString() => Value;
}

internal class Program
{
    public static void Main()
    {
        var items = new []
        {
            new Alpha { Value = "A" },
            new Alpha { Value = "B" },
            new Alpha { Value = "C", Children = new []
            {
                new Alpha { Value = "D", Children = new []
                {
                    new Alpha { Value = "E" },
                }},
                new Alpha { Value = "F" },
                new Alpha { Value = "G" },
                new Alpha { Value = "H", Children = new []
                {
                    new Alpha { Value = "I" },
                }},
            }},
            new Alpha { Value = "J", Children = new []
            {
                new Alpha { Value = "K" },
                new Alpha { Value = "L", Children = new []
                {
                    new Alpha { Value = "M" },
                }},
            }},
            new Alpha { Value = "N" },
            new Alpha { Value = "O", Children = new []
            {
                new Alpha { Value = "P" },
                new Alpha { Value = "Q", Children = new []
                {
                    new Alpha { Value = "R" },
                    new Alpha { Value = "S" },
                }},
                new Alpha { Value = "T" },
            }},
        };
        var ordered = items.ToRecursiveOrderList(a => a.Children);
        foreach (var item in ordered)
        {
            Console.WriteLine(item);
        }
    }
}

The output looks like this:

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T

Answer 2

public class NodeInfo
{
    public object Node { get; set; }
    public Queue<PropertyInfo> PropertiesToBeVisited{ get; set; }
}

public static class TypeExtensions
{
    public static bool IsComplex(this Type type)
    {
        return !type.IsValueType && type != typeof(string);
    }

    public static bool IsCollection(this Type type)
    {
        var collectionTypeName = typeof(ICollection<>).Name;
        return type.Name == collectionTypeName || type.GetInterface(typeof(ICollection<>).Name) != null;
    }
}

    public static void TraverseObjectTree(object data)
    {
        var currentNode = data;
        var currentNodeProperties = new Queue<PropertyInfo>(data.GetType().GetProperties());
        var nodeTracker = new Queue<NodeInfo>();
        while (currentNodeProperties.Count != 0 || nodeTracker.Count != 0)
        {
            if (currentNodeProperties.Count == 0 && nodeTracker.Count != 0)
            {
                var currentNodeInfo = nodeTracker.Dequeue();
                currentNode = currentNodeInfo.Node;
                currentNodeProperties = currentNodeInfo.PropertiesToBeVisited;
                continue;
            }
            var currentNodeProperty = currentNodeProperties.Dequeue();
            var currentNodePropertyType = currentNodeProperty.PropertyType;
            if (currentNodePropertyType.IsComplex())
            {
                var value = currentNode?.GetType().GetProperty(currentNodeProperty.Name)
                    ?.GetValue(currentNode, null);
                if (value != null)
                {
                    object node;
                    if (currentNodePropertyType.IsCollection())
                    {
                        var elementType = currentNodePropertyType.IsArray
                                ? value.GetType().GetElementType()
                                : value.GetType().GetGenericArguments()[0];
                        node = Activator.CreateInstance(elementType ?? throw new InvalidOperationException());
                    }
                    else
                    {
                        node = value;
                    }
                    nodeTracker.Enqueue(new NodeInfo
                    {
                        Node = currentNode,
                        PropertiesToBeVisited = currentNodeProperties
                    });
                    currentNode = node;
                    currentNodeProperties = new Queue<PropertyInfo>(node.GetType().GetProperties());
                    Console.WriteLine(currentNodeProperty.Name);
                    continue;
                }
            }
            Console.WriteLine(currentNodeProperty.Name);
        }
    }

This will do the job!!

Answer 3

Every recursion can be set as a loop.
For Depth Search, you can:

1. Put the root in a Queue (First in, first out)
2. While popping out the queue, you put all children of the item in queue
3. Save the item in the db

Edit: Added code per request

var nodeQueue = new Queue<Node>();
nodeQueue.Add(Tree.Root);
while (!nodeQueue.Empty())
{
    var item = nodeQueue.Pop();
    foreach(Node child in item.Children)
    {
        nodeQueue.Add(child);
    }
    db.Add(item.Data);
}   

Another way, which will take more time, is calculate the maximum amount of items in the tree (I assume it may not be balanced)

1. Run in a loop from 0 to MaxItems.
2. Each number, convert to binary.
3. Use 0 for left, and 1 for right.
4. For each digit, move accordingly in the tree. That way, each number represents a single node in your tree, and you can loop through the tree in a specific order.

Edit: Added code per request

var length = Tree.Count;
var depth = Tree.Depth;
var maxLength = Power(2,depth)-1
for (var i=0; i<maxLength; i++)
{
    db.Add(Tree.GetByNumber(i));
}

Let me know if you want more coded answer (If it's relevant)