Contents  Introduction  Recursion  Introduction to Trees  General Trees  Adding, Removing  and Processing  Nodes  Conclusion  Source code  Printable version  Discuss this article  in the forums The Series  Introduction  Binary Trees

Why recursion was used in these traversals

As I have said many times before, recursion is a powerful tool because it allows a large problem to be broken down into a much simpler problem. In the case of traversal, the beauty lies in being able to specify a small function which operates on only one node and allows the children to solve the problem for their children as well, thus allowing the root (or any parent node in the tree) to remain totally ignorant of the structure of its children. When you pre-order a tree, you process the root node, and then call preorder on each of it’s children. So when you preorder a child, it completes and pop’s execution back up to the root, allowing it to do the same thing to the next child, then the next, and so forth.

While it is possible to represent the traversal problem with an iterative solution, that solution would require a custom made stack, which is esentially using recursion with a different name. It is likely that the user defined stack will not be as efficient as the system stack, so an iterative solution would end up being slower.

The importance of recursion is somewhat downplayed in the traversal routines because each tree node maintains a pointer to the current child. Now, imagine a general tree implementation that used an array for its child list instead of a linked list. An array does not have an iterator object, and must use an index variable instead. In this case recursion helps because the index is stored on the stack at every level, and automatically restored when execution returns to each higher level. Recursion essentially helps the algorithm remember which path it traveled down.

In the end, recursion works so well with tree’s because a tree is esentially a recursive structure.

Conclusion

That's it for this tutorial. I had intended to include even more tree related stuff, all into one tutorial, but it ended up being too large. So next time, in part II, the tutorial will continue on with trees. Specifically, we'll be looking at binary trees, a specific subset of all trees, and the many various things that have been done with binary trees. I think I'll finish up at the third article, going into some of the more advanced tree structures. Until next time!