7
\$\begingroup\$

I've written some C# code to iterate through a Node[], listing all of its nodes in order (i.e. child elements are listed immediately after the parent).

Each Node is defined as follows,

class Node
{
    public string Name { get; set; }
    
    public List<Node> Children { get; set; } = new List<Node>();
    
    public bool HasChildren => Children.Count > 0;
    
    public Node(int n)
    {
        Name = $"Node #{n}";
    }
    
    public Node AddChild(Node n)
    {
        Children.Add(n);
        return this;
    }
    
    public override string ToString() => Name;
}

The collection of nodes to be iterated would be,

var nodes = new Node[]
{
    new Node(1),
    new Node(2),
    new Node(3)
        .AddChild(new Node(4))
        .AddChild(new Node(5))
        .AddChild(new Node(6)
            .AddChild(new Node(7)))
        .AddChild(new Node(8)
            .AddChild(new Node(9))
            .AddChild(new Node(10)))
};

...and output for the above would be 10 lines of "Node #", each followed by the number passed to the constructor of each (i.e. 1 to 10, in ascending order).

The code I've written to perfom the aforementioned task is,

var stack = new Stack<(Node[], int)>();

var i = 0;

while (i < nodes.Length)
{
    WriteLine($"{nodes[i]}");

    if (nodes[i].HasChildren)
    {
        // Stores away the current Node[] and the next index, to return to it once all children are iterated though.
        stack.Push((nodes, i + 1));
        
        // Makes the child Node[] the iteration target.
        nodes = nodes[i].Children.ToArray();

        // Resets the index to iterate all the children.
        i = 0;

        continue;
    }

    // If the current node is the last in the targeted Node[], and there are parent Node[]s from which this Node[] was switched to in the stack.
    if (i == nodes.Length - 1 && stack.Count > 0)
    {
        // Pop the stack until the popped Node[] isn't the last element, and assign it to the array being iterated.

        var (_target, _i) = stack.Pop();

        while (stack.Count > 0 && _i >= _target.Length)
        {
            (_target, _i) = stack.Pop();
        }

        nodes = _target;
        i = _i;

        continue;
    }

    ++i;
}

Any criticism of my algorithm? Does it work for Node[]s of any depth (level of child-ception ;)? Ways in which it can be optimized?

(T1, T2) is a ValueTuple.

\$\endgroup\$
4
  • \$\begingroup\$ You don't want to write a recursive function for it? \$\endgroup\$ Commented May 17, 2017 at 23:07
  • 2
    \$\begingroup\$ @EBrown a recursive function is simpler to understand and more elegant, but isn't the safest way as I understand. A deep enough Node[] would cause a stack overflow, wouldn't it? \$\endgroup\$ Commented May 17, 2017 at 23:09
  • \$\begingroup\$ Eventually, yes. But you can do things like tail-call recursion (google that, I'm on mobile unfortunately) which will not have such an effect. \$\endgroup\$ Commented May 17, 2017 at 23:10
  • \$\begingroup\$ @EBrown thanks, I shall look into that. However for the purpose of this question, let's assume that I don't want to go recursive :) \$\endgroup\$ Commented May 17, 2017 at 23:22

2 Answers 2

Reset to default
2
\$\begingroup\$

Collection initializer

You can improve and simplify your code by first tuning the Node.

  • make it IEnumerable<T> and consequently remove the Children and HasChildren properties because now we can use LINQ's Any
  • let the Name property take care of the formatting and keep the value clean in a dedicated field
  • replace AddChild with the Add method to be able to use collection initializer
  • replace the array with a root node

Example:

public class Node<T> : IEnumerable<Node<T>>
{
    private readonly T _value;

    private readonly List<Node<T>> _children = new List<Node<T>>();

    public Node(T value) => _value = value;

    public T Value => _value;

    public string Name => $"Node #{_value}";

    public void Add(Node<T> node) => _children.Add(node);

    public override string ToString() => Name;

    public IEnumerator<Node<T>> GetEnumerator() => _children.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Enumerator

Now you can improve the algorithm by using the Enumerator. There is no need for any indexes or tuples. What you need to do is to GetEnumerator from each node and MoveNext on it until it is now longer possible to continue or continue from a sub node if it contains Any.

The enumerator will keep the current state allowing you to continue iterating on child nodes and resume from the parent node later that's why you need to re-push the current node back to the stack.

An extension for the Node<T> could look like this:

public static IEnumerable<Node<T>> Flatten<T>(this Node<T> root)
{
    var stack = new Stack<IEnumerator<Node<T>>>();
    stack.Push(root.GetEnumerator()); // start with the root node

    yield return root; // return the root node
    
    while (stack.Any())
    {
        var node = stack.Pop();
        while (node.MoveNext())
        {
            yield return node.Current;
            if (node.Current.Any())
            {
                stack.Push(node); // re-add the node to continue later
                stack.Push(node.Current.GetEnumerator()); // continue from here now
                break; // we'll continue from "node" later, when node.Current is enumerated
            }
        }
    }
}

Example

You can now create nodes like arrays without confusing parenthesess when adding subnodes:

var nodes = new Node<int>(0)
{
    new Node<int>(1),
    new Node<int>(2),
    new Node<int>(3)
    {
        new Node<int>(4),
        new Node<int>(5)
        {
            new Node<int>(6)
            {
                new Node<int>(7)
            },
            new Node<int>(8)
            {
                new Node<int>(9),
                new Node<int>(10)
            },
            new Node<int>(11)
        }
    },
    new Node<int>(12)
};

after flattening it

nodes.Flatten().Select(n => n.Name).Dump();

you'll get:

Node #0 
Node #1 
Node #2 
Node #3 
Node #4 
Node #5 
Node #6 
Node #7 
Node #8 
Node #9 
Node #10 
Node #11 
Node #12
\$\endgroup\$
0
1
\$\begingroup\$

A typical iterative preorder traversal works like this:

Create a stack, push the root to the stack. While the stack is not empty, process the top element and push its children right-to-left to the stack.

So I suggest the following function to traverse the nodes:

static void IterateNodes(Node[] nodes)
{
    foreach (var node in nodes)
    {
        var stack = new Stack<Node>();
        stack.Push(node);
        while (stack.Count > 0)
        {
            Node current = stack.Pop();
            Console.WriteLine(current);
            var childrenRightToLeft = current.Children.AsEnumerable().Reverse();
            foreach (var child in childrenRightToLeft)
            {
                stack.Push(child);
            }
        }
    }
}

Note I don't have C#7 available, so I used some things like Console.WriteLine that you are free to change anyway you like.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.