C# replace recursive with while loop

Question

We have a node tree from a system, the Node model is like

Public class Node {
  public string Name { get; set; }
  public bool HasChildren { get; set; }
  public List<Node> Children { get; set; }
}

So, based on the Node model, the JSON of the node tree will be something like below:

{
  "Name": "Root",
  "HasChildren": true,
  "Children": [
    {
      "Name": "Node-1",
      "HasChildren": true,
      "Children": [
        {
          "Name": "Node-1-1",
          "HasChildren": false,
          "Children": []
        }
      ]
    },
    {
      "Name": "Node-2",
      "HasChildren": true,
      "Children": [
        {
          "Name": "Node-2-1",
          "HasChildren": false,
          "Children": [
            {
              "Name": "Node-2-1-1",
              "HasChildren": false,
              "Children": []
            }
          ]
        },
        {
          "Name": "Node-2-2",
          "HasChildren": false,
          "Children": [
            {
              "Name": "Node-2-2-1",
              "HasChildren": false,
              "Children": []
            }
          ]
        }
      ]
    }
    ...
  ]
}

Now, I'd like to save every node in a flattened array or list. To traverse all the nodes, I know I can recursively get them. But, using recursion causes a big usage of memory.
Is there a way of using the loop logic, like while, for, or foreach logic to do the same?

"Is there a way...". Almost certainly. What have you tried and where are you stuck? This site is not a place where you tell us what you want and we write the code for you. Consider the logic required, make you best attempt to implement that logic in code and then, if it doesn't work, show us what you've done and explain exactly what the issue with it is. — John
– John, Commented Sep 23, 2022 at 5:03
It is not true that recursion uses more memory than other methods of parsing. There is some small amount of overhead memory that is used when you call a method. Recursion can method many times but the amount of memory isn't huge. The size of the tree structure should not be inside the recursion methods and will be the same if recursion is used or recursion is not used. — jdweng
– jdweng, Commented Sep 23, 2022 at 5:07
The recursive solution would use the stack to remember where you're up to. A loop will need some other data structure to remember that. Using the stack has advantages, as you can easily mix data types together without any extra heap allocations. — Jeremy Lakeman
– Jeremy Lakeman, Commented Sep 23, 2022 at 5:59

JonasH · Accepted Answer · 2022-09-23 06:41:51Z

3

My goto tree iterator looks like this:

public static IEnumerable<T> DepthFirst<T>(T self, Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var child in selector(current))
        {
            stack.Push(child);
        }
    }
}

Called like DepthFirst(myRootNode, n => n.Children). This generic, so it can be reused for all different kinds of tree representations. It is also lazily evaluated.

This variant iterates in a depth first order, but it is trivial to change the stack to a queue to get a breadth first ordering.

answered Sep 23, 2022 at 6:41

JonasH

38.5k2 gold badges16 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

SomeBody · Accepted Answer · 2022-09-23 08:06:44Z

2

With this code, you can do it in a loop:

List<Node> result = new List<Node> { node };
        bool finished = false;
        int start = 0;
        while(!finished)
        {
            int end = result.Count;
            for(int i = start; i < end; i++)
            {
                if(result[i].HasChildren)
                {
                    result.AddRange(result[i].Children);
                }
            }
            
            if(result.Count == start)
            {
                finished = true;
            }
            start = end;
        }

First, we add the root node to the result list. Then we enter a loop, which has another loop in it. This inner loop goes through all entries which have been added in the last iteration. In the first iteration, the inner loop goes only through the root node. The inner loop adds then all children of those nodes to the result list. The outer loop will run until the inner loop doesn't add any further nodes.

Note that it will change the order of the flattened list. The children of a node won't be directly behind their parent. Instead, the more down a node is in the hierarchy, the more in the end of the list the node will be. I hope this is ok for you, since you didn't write anything about your preferred order.

Online demo: https://dotnetfiddle.net/Rx67kK

edited Sep 23, 2022 at 8:06

answered Sep 23, 2022 at 6:33

SomeBody

8,9102 gold badges20 silver badges38 bronze badges

2 Comments

JonasH Over a year ago

The ordering of this can be called "Breadth-first". Also, all children will be placed behind their parent, but not immediately behind.

CF7 Over a year ago

Thank you @SomeBody, I do like this solution and your explanation. It does what exactly I want to achieve. Thank you again!

Collectives™ on Stack Overflow

C# replace recursive with while loop

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related