Introduction:
A lot of components in the C# environment are essentially a K-ary [kay-er-ee] tree. From tree-view nodes, to serialising a type via reflection, to directory listings to menu hierarchies, and so on.
Often we need to iterate through these types of structures, or our own trees, and we just write some code to do it as needed. This code is often problematic as it’s non-trivial to do well, because:
- It’s complex to do certain traversals in an iterative manor. (non recursive);
- Traversal is prone to bugs, as there are many edge cases;
- Software hangs if a circular reference exists and you don’t catch it;
- Unit-testing of once-off code is often neglected;
- Examining / verifying correct behaviour of tree traversal algorithms is difficult in the debugger.
Wanting to rid myself of this re-occurring situation I built a few helper methods to do the following traversals iteratively:
- Depth First Pre Order
- Depth First Post Order,
- Breadth First
The helpers are generic [BYO data type] and dont require a specific interface. You just supply a Func to return a nodes sub nodes. Thus you can drop a working tested algorithm onto whatever situation you encounter.
Iteration
Example:
- Made using an example data type “Node”
- See the unit-tests at the bottom of the page for implementation
- First it shows using a foreach loop on a depth first pre-order iterator
- Then is shows using a breadth-first iterator to convert a tree to an array using Linq.
/*
* Test tree
* A
* / | \
* B C D
* / | | \
* E F G H
* / | / | \
* I J K L M
*/
Node<char> tree = Node<char>.TestTree();
//EXAMPLE 1: Pre-order traversal via foreach loop
foreach(var node in Misc.EnumerateNodes(tree,
N => N.Nodes,
NodeVisitOrder.DepthFirstPreOrder))
{
Console.Out.Write(node.Item);
}
Console.Out.WriteLine();
//outputs ABEIJFCDGKLMH
//EXAMPLE 2: Creating an array via breadth first traversal
string s = new String(Misc.EnumerateNodes(tree, N => N.Nodes, NodeVisitOrder.BredthFirst)
.Select(N => N.Item)
.ToArray());
Console.Out.WriteLine(s);
//outputs ABCDEFGHIJKLM
This was a simplistic example, but it works, its unit-tested, its efficient and non-recursive. It all ties into linq and IEnumerable so many neat tricks are possible.
Lets examine the crucial line in detail.
EnumerateNodes(tree, N => N.Nodes, NodeVisitOrder.DepthFirstPreOrder)
- The first parameter is the root node. This is method is generic, so any class type will do.
- The second is a lambda expression for an enumerable set of sub-nodes
- The third is the traversal method.
Another example of how flexible the method is, using DirectoryInfo as the node, and iterating over all subdirectories:
- This time we use the optional forth parameter to enable circular reference checking. this prevents any chance of an infinite loop
DirectoryInfo root = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
var dirs = Misc.EnumerateNodes(
root,
N => { try { return N.GetDirectories(); }
catch (Exception) { return null; } },
NodeVisitOrder.DepthFirstPreOrder,
CircularRefernceBehaviour.Skip);
foreach (var dir in dirs)
{
}
Duplication
Often you just need to copy one tree structure to another (possibly of a different type):
- Loading a directory structure into a TreeView control
- Turning a tree of commands into Menu Items
- Working with expression parsing and evaluation
- Just making a deep copy of a tree structure
/*
* Test tree
* A
* / | \
* B C D
* / | | \
* E F G H
* / | / | \
* I J K L M
*/
Node<char> tree = Node<char>.TestTree();
TreeNode n = Misc.RebuildTree(tree,
N => N.Nodes,
N => new TreeNode("" + N.Item),
(T, N) => T.Nodes.AddRange(N.ToArray()));
Neeto, one line of code, and our tree is duplicated into a TreeView (or whatever) in a efficient, reliable manor.
RebuildTree takes five parameters:
- The root of the tree to be copied.
- Func for an enumerating sub-nodes in the source structure
- Func to create a new destination node form a source node
- Just the data of the node, Leave the child nodes unpopulated
- Action to add a collection of Nodes to an existing node (destination structure)
- Circular reference checking behaviour
Core Algorithms
Depth First Pre-Order
- Note: visitOk(…) returns true unless a circular reference is detected.
- This works by feeding al nodes onto a stack, a basic way to resolve the recursion.
- Child nodes are pushed in reverse order, so they are pop’ed in the correct order.
LinkedList list = new LinkedList();
HashSet visited = new HashSet();
list.AddLast(node);
while (list.Count > 0)
{
T item = list.Pop();
if (visitOk(item, visited, checkType))
{
yield return item;
list.AddLastAll(getSubNodesSafe(item, getSubNodes).Reverse());
}
}
Depth First Post-Order
- Depth First Post-Order is actually pretty tricky, a few algorithms exist.
- This one initially traverses the entire tree O(n) to fill a stack, then returns each item in the stack.
- The overall time is O(n), with the first iteration being O(n) and all subsequent iterations being O(1)
- There s a requirement for extra memory for this to work, but its not too bad.
LinkedList list = new LinkedList();
HashSet visited = new HashSet();
Stack output = new Stack();
list.AddLast(node);
while (list.Count > 0)
{
T item = list.Pop();
if (visitOk(item, visited, checkType))
{
output.Push(item);
list.AddLastAll(getSubNodesSafe(item, getSubNodes));
}
}
foreach (T item in output)
{
yield return item;
}
Breadth First
- This works by feeding al nodes onto a queue, as opposed to the depth first – pre order, which uses a stack.
- This time Child nodes are not added in reverse order, however
LinkedList list = new LinkedList();
HashSet visited = new HashSet();
list.AddLast(node);
while (list.Count > 0)
{
T item = list.Dequeue();
if (visitOk(item, visited, checkType))
{
yield return item;
list.AddLastAll(getSubNodesSafe(item, getSubNodes));
}
}
break;
}
Source Code:
/*
Available under the BSD 3-Clause License
Copyright (c) 2015, Dr Warren Creemers All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using WD_toolbox;
namespace WD_toolbox
{
public enum NodeVisitOrder { DepthFirstPreOrder, DepthFirstPostOrder, BredthFirst }
public enum CircularRefernceBehaviour { DontCheck, ThrowException, Skip }
public class NodeTraversalException : Exception
{
public NodeTraversalException(string message) : base(message) { }
public NodeTraversalException() : base() { }
public static NodeTraversalException VisitedTwice(object item) {return new NodeTraversalException("Node already visied: " + item.ToString());}
}
public static class Misc
{
/// <summary>
/// Enumerates any Tree/graph in a non-recursive manor.
/// Does not check for circularReferences.
/// </summary>
/// <param name="node">Root node.</param>
/// <param name="getSubNodes"> Get the sub-nodes of any given node.</param>
/// <param name="order">The visit order.</param>
/// <param name="checkType">If circular references should be checked, and how to handle them.
/// Note (1): Checks repeated node, which is not nesesiarly a circular reference (but all circulare references have a repeated node).
/// Note (2): performance hit reduced if node generates a good hashcode.
/// </param>
public static IEnumerable<T> EnumerateNodes<T>( T node,
Func<T, IEnumerable<T>> getSubNodes,
NodeVisitOrder order = NodeVisitOrder.DepthFirstPreOrder,
CircularRefernceBehaviour checkType = CircularRefernceBehaviour.DontCheck)
where T : class
{
if (node != null) //assuming null indicats an empty tree
{
//this acts as a stack or queue to resolve the recursion
LinkedList<T> list = new LinkedList<T>();
HashSet<T> visited = new HashSet<T>();
switch (order)
{
case NodeVisitOrder.DepthFirstPreOrder:
list.AddLast(node);
while (list.Count > 0)
{
T item = list.Pop();
if (visitOk(item, visited, checkType))
{
yield return item;
list.AddLastAll(getSubNodesSafe(item, getSubNodes).Reverse());
}
}
break;
case NodeVisitOrder.DepthFirstPostOrder:
//This has a side effects, the first iteeration is slow (also memory consuming)
//as the entire structure is copied into a stack
Stack<T> output = new Stack<T>();
list.AddLast(node);
while (list.Count > 0)
{
T item = list.Pop();
if (visitOk(item, visited, checkType))
{
output.Push(item);
list.AddLastAll(getSubNodesSafe(item, getSubNodes));
}
}
foreach (T item in output)
{
yield return item;
}
break;
case NodeVisitOrder.BredthFirst:
list.AddLast(node);
while (list.Count > 0)
{
T item = list.Dequeue();
if (visitOk(item, visited, checkType))
{
yield return item;
list.AddLastAll(getSubNodesSafe(item, getSubNodes));
}
}
break;
}
}
}
// Because getSubNodes(T) may return null to indicate no nodes.
private static IEnumerable<T> getSubNodesSafe<T>(T node, Func<T, IEnumerable<T>> getSubNodes)
{
if ((node != null) && (getSubNodes != null))
{
IEnumerable<T> subNodes = getSubNodes(node);
return (subNodes != null) ? subNodes : new List<T>();
}
return new List<T>();
}
private static bool visitOk<T>(T item, HashSet<T> visited, CircularRefernceBehaviour checkType)
{
if (checkType != CircularRefernceBehaviour.DontCheck)
{
if (visited.Contains(item))
{
// error
if (checkType == CircularRefernceBehaviour.ThrowException)
{
throw NodeTraversalException.VisitedTwice(item);
}
return false; //indicate it's not ok to visit (ie skip)
}
//no error
visited.Add(item);
return true;
}
//no check
return true;
}
/// <summary>
/// Copies a tree structure. (useful in copying a tree structure to a tree view).
/// </summary>
/// <typeparam name="A">The node type of the tree to copy.</typeparam>
/// <typeparam name="B">The destination node type.</typeparam>
/// /// <param name="getSubNodes"> Get the sub-nodes of any given node.</param>
/// <param name="newNode">To create a simple non-recursive copy of a node.</param>
/// <param name="addSubNodes"></param>
/// <param name="checkType"> Type of circular reference checking to perform.</param>
/// <returns></returns>
public static B RebuildTree<A, B>(A srcNode,
Func<A, IEnumerable<A>> getSubNodes,
Func<A, B> newNode,
Action<B, IEnumerable<B>> addSubNodes,
CircularRefernceBehaviour checkType = CircularRefernceBehaviour.DontCheck)
where A : class
where B : class
{
return RebuildTree(srcNode, getSubNodes, newNode, addSubNodes, P => true, checkType);
}
/// <summary>
/// Copies a tree structure. (useful in copying a tree structure to a tree view).
/// </summary>
/// <typeparam name="A">The node type of the tree to copy.</typeparam>
/// <typeparam name="B">The destination node type.</typeparam>
/// /// <param name="getSubNodes"> Get the sub-nodes of any given node.</param>
/// <param name="newNode">To create a simple non-recursive copy of a node.</param>
/// <param name="addSubNodes"></param>
/// <param name="where"></param>
/// <param name="checkType"> Type of circular reference checking to perform.</param>
/// <returns></returns>
public static B RebuildTree<A, B>( A srcNode,
Func<A, IEnumerable<A>> getSubNodes,
Func<A, B> newNode,
Action<B, IEnumerable<B>> addSubNodes,
Predicate<A> where,
CircularRefernceBehaviour checkType = CircularRefernceBehaviour.DontCheck)
where A : class
where B : class
{
LinkedList<Tuple<A, B>> list = new LinkedList<Tuple<A, B>>();
HashSet<A> visited = new HashSet<A>();
B newRootNode = null;
list.AddLast(new Tuple<A, B>(srcNode, null));
while (list.Count > 0)
{
var tuple = list.Pop();
A item = tuple.Item1;
B parent = tuple.Item2;
if (visitOk(item, visited, checkType))
{
if (where(item))
{
B newItem = newNode(item);
if (newRootNode == null) //root node
{
newRootNode = newItem;
}
safeAddSubNode(parent, newItem, addSubNodes);
list.AddLastAll(getSubNodesSafe(item, getSubNodes).Reverse().Select(N => new Tuple<A, B>(N, newItem)));
}
}
}
//done
return newRootNode;
}
private static void safeAddSubNode<B>(B parent, B child, Action<B, IEnumerable<B>> addSubNodes)
{
if ((addSubNodes != null) && (parent != null) && (child != null))
{
addSubNodes(parent, new B[] { child });
}
}
}
}
Requires The following Extension class to make LinkedList sane.
/*
Available under the BSD 3-Clause License
Copyright (c) 2015, Dr Warren Creemers All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/// <summary>
/// These extensions make usage of the LinkedList more consise.
/// </summary>
public static class LinkedListExtension
{
/// <summary>
/// Pops the last value of the linked list.
/// </summary>
/// <returns> Value of the (formerly) last item in the list. </returns>
/// <exception cref="System.InvalidOperationException"> The LinkedList is empty.</exception>
public static T Pop<T>(this LinkedList<T> list)
{
T item = list.Last.Value;
list.RemoveLast(); //throws InvalidOperationException
return item;
}
/// <summary>
/// Dequeues the first value of the linked list.
/// </summary>
/// <returns> Value of the (formerly) first item in the list. </returns>
/// <exception cref="System.InvalidOperationException"> The LinkedList is empty.</exception>
public static T Dequeue<T>(this LinkedList<T> list)
{
T item = list.First.Value;
list.RemoveFirst(); //throws InvalidOperationException
return item;
}
/// <summary>
/// Gets the last value of the linked list.
/// </summary>
/// <returns> Value of the last item in the list. </returns>
/// <exception cref="System.InvalidOperationException"> The LinkedList is empty.</exception>
public static T PeekLast<T>(this LinkedList<T> list)
{
if (list.Count <= 0)
{
throw new InvalidOperationException("LinkedList is empty (call to PeekLast)");
}
T item = list.Last.Value;
return item;
}
/// <summary>
/// Gets the last value of the linked list.
/// </summary>
/// <returns> Value of the last item in the list. </returns>
/// <exception cref="System.InvalidOperationException"> The LinkedList is empty.</exception>
public static T PeekFirst<T>(this LinkedList<T> list)
{
if (list.Count <= 0)
{
throw new InvalidOperationException("LinkedList is empty (call to PeekFirst)");
}
T item = list.First.Value;
return item;
}
/// <summary>
/// Addss items to the end of the list.
/// </summary>
/// <param name="items">Items to add.</param>
public static void AddLastAll<T>(this LinkedList<T> list, IEnumerable<T> items)
{
foreach (T item in items)
{
list.AddLast(item);
}
}
/// <summary>
/// Addss items to the end of the list.
/// </summary>
/// <param name="items">Items to add.</param>
public static void AddFirstAll<T>(this LinkedList<T> list, IEnumerable<T> items)
{
foreach (T item in items)
{
list.AddFirst(item);
}
}
}
Unit Tests:
[TestMethod()]
public void EnumerateNodesTest()
{
/*
* Test tree
* A
* / | \
* B C D
* / | | \
* E F G H
* / | / | \
* I J K L M
*/
Node<char> tree = Node<char>.TestTree();
Node<char> coruptTree = Node<char>.TestTree();
//point L to A
coruptTree.Nodes[2].Nodes[0].Nodes[1].Nodes.Add(coruptTree);
//DepthFirstPreOrder
string res = new String(Misc.EnumerateNodes(tree, N => N.Nodes,
NodeVisitOrder.DepthFirstPreOrder,
CircularRefernceBehaviour.ThrowException).Select(N => N.Item).ToArray());
//System.Diagnostics.Trace.WriteLine("Hello World");
Assert.AreEqual("ABEIJFCDGKLMH", res);
//DepthFirstProstOrder
res = new String(Misc.EnumerateNodes(tree, N => N.Nodes,
NodeVisitOrder.DepthFirstPostOrder,
CircularRefernceBehaviour.ThrowException).Select(N => N.Item).ToArray());
Assert.IsTrue(res == "IJEFBCKLMGHDA");
//BredthFirst
res = new String(Misc.EnumerateNodes(tree, N => N.Nodes,
NodeVisitOrder.BredthFirst,
CircularRefernceBehaviour.ThrowException).Select(N => N.Item).ToArray());
Assert.AreEqual("ABCDEFGHIJKLM", res);
//just to check no exception thrown
TreeNode n = Misc.RebuildTree(tree,
N => N.Nodes,
N => new TreeNode("" + N.Item),
(T, N) => T.Nodes.AddRange(N.ToArray()),
CircularRefernceBehaviour.ThrowException);
//Check an exception is thrown for curupted tree
try
{
n = Misc.RebuildTree(coruptTree,
N => N.Nodes,
N => new TreeNode("" + N.Item),
(T, N) => T.Nodes.AddRange(N.ToArray()),
CircularRefernceBehaviour.ThrowException);
Assert.Fail("Should never reach this line of code");
}
catch (Exception)
{
}
//Just handle a corupt tree by not going backward.
n = Misc.RebuildTree(coruptTree,
N => N.Nodes,
N => new TreeNode("" + N.Item),
(T, N) => T.Nodes.AddRange(N.ToArray()),
CircularRefernceBehaviour.Skip);
//NB: Infinite loop on fail
}
public class Node<T>
{
public List<Node<T>> Nodes = new List<Node<T>>();
public T Item;
public Node(T item, IList<Node<T>> nodes = null)
{
Item = item;
if (nodes != null)
{
Nodes.AddRange(nodes);
}
}
private static Node<T> NODE<T>(T item, params Node<T>[] Nodes)
{
return new Node<T>(item, Nodes);
}
public static Node<char> TestTree()
{
/*
* Test tree
* A
* / | \
* B C D
* / | | \
* E F G H
* / | / | \
* I J K L M
*/
Node<char> tree =
NODE('A',
NODE('B',
NODE('E',
NODE('I'),
NODE('J')
),
NODE('F')
),
NODE('C'),
NODE('D',
NODE('G',
NODE('K'),
NODE('L'),
NODE('M')
),
NODE('H')
)
);
return tree;
}
}
}
WDLib Library:
This is part of my personal toolbox, WDLib (in the misc class, which is abridged for clarity on this page). I am moving to open source the library at the moment.
Limitations and Usage:
- The circular reference check just checks for a repeated node, which is not necessarily a circular reference (but all circular references have a repeated node). This may deny some malformed trees that could otherwise be safely parsed. Checking can always be disabled if this is your intent.
- Be aware the first iteration of the Depth First Post-Order has a O(n) overhead.
Contact / Feedback
[Sorry I had to remove this, because hundreds of spam emails about SEO]
