Practical Iterative K-ary Tree (aka n-ary, n-tree) Traversal in C#. A surprisingly useful tool for the average programmer.

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

* 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)

1	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)
{
}

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

Available under the BSD 3-Clause License

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

Available under the BSD 3-Clause License

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.

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.

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

[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]