Critical Development

Language design, framework development, UI design, robotics and more.

Four Traversal Patterns for Tree<T>

Posted by Dan Vanderboom on April 5, 2010

[Updated 8/14/2014] The source code for this library can be found here at GitHub. Also check out my blog post announcing it.

This is an update to my original article on a non-binary tree data structure.  After receiving multiple requests to complete this, here it is.  The updated source code can be downloaded here.

To illustrate the four possible traversal types, the following tree data structure will be used in all of my examples.

image

The enum TreeTraversalType has two possible values: DepthFirst and BreadthFirst.  The other enum involved, TreeTraversalDirection, determines which end of the tree it starts from: TopDown or BottomUp.  There are four possible combinations of these two values, which will each be presented separately.

Depth-First, Top-Down

This traversal strategy involves starting at the root and digging as deep into the tree whenever possible.  The order of nodes yielded by our example tree structure would be a-b-d-e-c-f-g.

image

Depth-First, Bottom-Up

Because we’re moving bottom-up in this case, the first thing we have to do is dive to the bottom of the first branch we find.  We skip past a and b, and find d with no children.  D is therefore the first node we’ll yield.  E is it’s peer, so that comes next.  From e, we move up the tree to b.  A is the root, so it has to be the last node yielded, so we’re going to dive into the c branch next, yield f and g, and then yield c and finally a.  The order is: d-e-b-f-g-c-a.

image

Breadth-First, Top-Down

When we traverse breadth-first, we’re moving through the tree in levels.  With Top-Down, we start with the root a, then move to the second level with b and c, and then finally move to the third level to yield d-e-f-g.

image

Breadth-First, Bottom-Up

The final traversal is the one I had the most trouble with, and I ended up cheating a little by reversing the Breadth-First, Top-Down traversal.

image

Conclusion

Now, with a call to GetEnumerable on a node object, you can specify which of these four traversal patterns to use.  Here is an example of how that code looks:

foreach (SimpleTreeNode<string> node in 
    root.GetEnumerable(TreeTraversalType.DepthFirst, TreeTraversalDirection.TopDown))
{
    // ...
}

 

Advertisements

4 Responses to “Four Traversal Patterns for Tree<T>”

  1. George said

    Shouldn’t depth-first bottom-up be:

    g,f,c
    e,d,b
    a

    ?

  2. matt said

    Great article, thanks for taking the time.

    Can I just clarify something – what do the ‘tree’ and ‘subtree’ aliases buy you? I don’t see the need for them, but I feel I’m missing something.

    Thanks

    • Dan Vanderboom said

      There is no real need for them. What I was thinking at the time was that they may provide additional clarity: for example, in the event that you have a single primary tree, and from that you want to extract or point to specific subtrees of that tree. Having a separate Subtree type in Intellisense would be a good indicator of what you’re looking at while debugging.

  3. Romain S said

    Hi Dan,

    I am struggling to get what is happening in the GetDepthFirstEnumerable(TreeTraversalDirection TraversalDirection)

    I understand that it traverses a branch of a tree top to bottom or bottom to up, but after having studied your code, and documented myself on how works iterators, I am still struggling what those 10 lines of code does:

    private IEnumerable<ComplexTreeNode> GetDepthFirstEnumerable(TreeTraversalDirection TraversalDirection)
    {
    if (TraversalDirection == TreeTraversalDirection.TopDown)
    yield return this;

    foreach (ComplexTreeNode child in Children)
    {
    var e =
    child.GetDepthFirstEnumerable(TraversalDirection).GetEnumerator();
    while (e.MoveNext())
    {
    yield return e.Current;
    }
    }

    if (TraversalDirection == TreeTraversalDirection.BottomUp)
    yield return this;
    }

    THere are 2 yield return statements, that when executed, do not return a value to the calling method (that uses the for each loop on the GetDepthFirstEnumerable() method) but instead, from what I understand, will instantiate another iterator on another node and then excecute the body of the GetDepthFirstEnumerable() on it :

    For instance, when yield return e.Current is executed and that this is node a (in your schema) then it will instead of returning node a to the calling method, will start the execution of the GetDepthFirstEnumerable() method on node b (in the case of a top down approach).

    I get the purpose once again, but I don’t quite get maybe the role of the yield return statements, why at some point returning this and at some point e.Current ?

    Could you explain a bit more in the details the concept and mechanisms you used in the GetDepthFirstEnumerable() method for instance ?

    Thanks a lot by advance, I must say your articles are for most of them really great.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: