Tree traversal without recursion

Tree traversal is a classic algorithm problem that is often presented in introductory classes as an example of how recursion could be used to simplify a seemingly complicated problem. A tree could be traversed in a wide range of ways with the two broad categories termed as depth-first and breadth-first traversal. In my experience I have seen more applications of depth-first traversal which further includes different traversals called in-order, pre-order and post-order traversal. For example, consider a rudimentary three level binary tree shown below.

      1                 In order: 4, 2, 5, 1, 6, 3, 7
    /   \ 
   2     3             Pre order: 1, 2, 4, 5, 3, 6, 7
 /  \   /  \
4    5 6    7         Post order: 4, 5, 2, 6, 7, 3, 1

The corresponding in-order, pre-order and post-order traversals are shown next to the tree. In simple terms, in the in-order traversal one traverses the left branch followed by the root and finally traverse the right branch. In case of pre-order one visits the root followed by traversing the left and then the right branch. Assuming that the tree is implemented by a “Node” structure as shown below,

we can easily implement the three fundamental traversals using recursive routines as shown below.

Implementing the traversals using recursion is pretty straightforward and intuitive. But recently I was presented with a problem of implementing the said traversals without recursion. It would be useful to recall that recursive function calls are typically implemented by compilers using stacks resulting in the famous stackoverflow error when one accidentally implements an infinite recursion. A well known example of a non-stack based recursion is the tail recursion used in functional languages where a properly written tail recursion is implemented as a jump instead of tracking the function calls with a stack. So it is natural to believe that we can implement the above traversals using a stack based approach instead of a recursive function call. It is also natural to assume that the traversal will be conducted using a while loop since we do not have apriori knowledge of the tree structure. But the question remains, what conditional statement would you use for the while statement? I assumed that we can have a pointer named currNode to keep track of the current node under investigation and the while loop will last as long as currNode is not NULL. This was my folly as it results in additional complications and a inelegant code. Below is the first attempt.

The code attempts to push only legitimate pointer locations (not NULLs) onto the stack. And anytime it encounters a node without a left child it will print out its value, else it will push the current node onto the stack and sets the current node as the left child. The code as it stands has a bug. Once we pop a value from the stack the code checks for its left child once again even though the fact that the node was popped from the stack should imply that its left child has already been traversed. We could fix this problem by adding a simple flag to keep track of whether the current node was popped from a stack, in which case we need not traverse its left child.

This version should perform as expected but it is unnecessarily complicated and cluttered with the need for a flag variable. This was not a very satisfying solution. On further thought I reduced the reason for the problem to the bad choice for the while conditional. In my zeal to avoid currNode carry a NULL value until the very end I ended up choosing a non optimum conditional for the while loop. A simple and quick change sets the while conditional as while(currNode!=NULL||!myStack.empty()). The following revised version shows how such a simple change drastically improves the code clarity, readability and compactness.

The reason for this post is to present the cautionary tale that a bad choice in a single statement in your code could have a cascading effect leading to the need for inelegant patches like the flag variable in my case. It would serve really well to think through the key parts of your code and look at the various alternatives and how it will affect the rest of the code in the program. Although while(currNode!=NULL) looks simpler than while(currNode!=NULL||!myStack.empty()) it is clear that you will pay the price for the bad choice at a later point.

For the sake of completeness I have included the complete code with both recursive and non-recursive implementations of the various traversals along with a main function that runs a test case.