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.

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.

  • 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

 

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

 

Neeto, one line of code, and our tree is duplicated into a TreeView (or whatever) in a efficient, reliable manor.

RebuildTree takes five parameters:

  1. The root of the tree to be copied.
  2. Func for an enumerating sub-nodes in the source structure
  3. Func to create a new destination  node form a source node
    • Just the data of the node, Leave the child nodes unpopulated
  4. Action to add a collection of Nodes to an existing node (destination structure)
  5. 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.

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.

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

 

Source Code:

 

Requires The following Extension class to make LinkedList sane.

Unit Tests:

 

 

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