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
.
2 Answers 2
Collection initializer
You can improve and simplify your code by first tuning the Node
.
- make it
IEnumerable<T>
and consequently remove theChildren
andHasChildren
properties because now we can use LINQ'sAny
- let the
Name
property take care of the formatting and keep thevalue
clean in a dedicated field - replace
AddChild
with theAdd
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
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.
Node[]
would cause a stack overflow, wouldn't it? \$\endgroup\$