Tree concept not working with c# iterators-CodePudding

I'm learning c# iterators and I'm trying to make them work in this kind of tree like structure but unfortunately all I can get is to enumerate the root and their direct children.

public class Node : IEnumerable<Node>
{
  private Node Parent = null;
  private List<Node> Children = new List<Node>();
  public string Name { get; private set; };
  
  public Node(string name)
  {
    Name = name;
  }
  public Node AddChild(Node child)
  {
    Children.Add(child);
    child.Parent = this;
    return child;
  }
  
  public IEnumerator<Node> GetEnumerator()
  {
    yield return this;
    foreach (var x in Children)
      yield return x;
  }

  IEnumerator IEnumerable.GetEnumerator()
  {
    return GetEnumerator();
  }
}

I've tried to go recursive with a static method but IEnumerator doesn't allow it as it has to return T. Could anyone what's wrong with this approach? Thanks in advance.

Usage example:

Node root = new Node("html");
root.AddChild(new Node("body")).AddChild(new Node("i")).AddChild(new Node("b"));

foreach(var m in root)
  Console.WriteLine(m.Name);

CodePudding user response：

you have one foreach missing

public IEnumerator<Node> GetEnumerator()
  {
    yield return this; // returns current item
    foreach (var x in Children) // iterates over children list
         foreach (var c in x) // iterates over child enumerator 
             yield return c; // returns child and grandchildren
  }

CodePudding user response：

Here's one approach https://dotnetfiddle.net/pRqmbM

    public IEnumerator<Node> GetEnumerator()
    {
        yield return this;
        foreach (var x in Children)
        {
            var enumerator = x.GetEnumerator();
            if (enumerator.MoveNext())
            {
                do
                {
                    yield return enumerator.Current;

                }while(enumerator.MoveNext());
            }
        }
    }

Another idea would be to use a visitor pattern and walk the tree adding each node to a list then iterating over that.

CodePudding user response：

While the solution proposed by Rafal and others is correct, and probably the simplest solution. This has some potential problems when iterating large trees.

The runtime will create an object for each iterator, so when iterating over the tree you will create one iterator object for each node. While creating objects is cheap, it starts adding up when creating millions of them. And advancing a node may involve as many method calls as there are levels in the tree.

Because of this I would suggest creating a single iterator that processes the entire tree:

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);
        }
    }
}

You can call this from a member method like

public IEnumerator<Node> GetEnumerator()
  => DepthFirst(this, node => node.Children).GetEnumerator();

This still uses a iterator block for traversing the tree, but it will only need to create a constant number of objects when called. It also keeps a explicit stack, so should be safe for any tree depths.