preorder traversal

Trees it turns out are a lot harder than lists. For the first time I was clueless on a way forward without looking for a hint in the book.

The problem is to just do a simple preorder traversal of a tree and print out every node. Recursively this is a trivial exercise:

But then the next problem is to do the same thing without recursion. You can't just do a nested loop, because each level of the tree needs a new loop but we don't know how to many levels we need.

The solution is to replicate the call stack you get from recusion automatically with (surprise) a stack. So implement a stack, and store the "to do" nodes on the stack.

So since we're doing preorder traversal, you traverse left on each level and store the right node if one exists on the stack. When you run out of left nodes to traverse, pop a node from the stack and continue.

This is a really nice problem for gaining a good understanding of what's happening conceptually on the call stack when recursing.

(The little schemer is another great little book for understanding recursion, which lets you do fun stuff like implement addition and multiplication with recursive functions.)


Leave a comment -


I'm a .NET, PHP, Python, and Javascript developer. Also Project Manager, Scrum Master, and Juilliard trained violist. You cannot connect with me on Facebook, Twitter, or LinkedIn so don't ask.