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,

1 2 3 4 5 |
struct Node{ int value; Node *right; Node *left; }; |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void inOrderTraversal(Node *root){ if (root->left!=NULL) inOrderTraversal(root->left); cout<<root->value<<", "; if (root->right!=NULL) inOrderTraversal(root->right); } void preOrderTraversal(Node *root){ cout<<root->value<<", "; if (root->left!=NULL) preOrderTraversal(root->left); if (root->right!=NULL) preOrderTraversal(root->right); } void postOrderTraversal(Node *root){ if (root->left!=NULL) postOrderTraversal(root->left); if (root->right!=NULL) postOrderTraversal(root->right); cout<<root->value<<", "; } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void inOrderTraversalNoRecurse(Node *root){ Node *currNode = root; stack<Node*> myStack; while ( currNode!=NULL){ if( currNode->left !=NULL){ myStack.push(currNode); currNode = currNode->left; } elseif (currNode->right!=NULL){ cout << currNode->value<<", "; currNode = currNode->right; } else{ cout << currNode->value << ", "; if(!stack.isempty()){ currNode=mystack.top(); mystack.pop(); } else currNode=NULL; } } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
void inOrderTraversalNoRecurse(Node *root){ Node *currNode = root; stack<Node*> myStack; int flag=0; //flag==1 will imply that the currNode was popped from the stack while ( currNode!=NULL && flag==0){ if( currNode->left !=NULL){ myStack.push(currNode); currNode = currNode->left; flag=0; } elseif (currNode->right!=NULL){ cout << currNode->value<<", "; currNode = currNode->right; flag=0 } else{ cout << currNode->value << ", "; if(!stack.isempty()){ currNode=mystack.top(); mystack.pop(); flag=1; } else currNode=NULL; } } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void inOrderTraversalNoRecurse(Node *root){ Node *currNode = root; stack<Node*> myStack; while ( currNode!=NULL || !myStack.empty()){ if( currNode !=NULL){ myStack.push(currNode); currNode = currNode->left; } else{ currNode = myStack.top();myStack.pop(); cout<<currNode->value<<", "; currNode = currNode->right; } } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include<iostream> #include<stack> using namespace std; struct Node{ int value; Node *right; Node *left; }; void inOrderTraversal(Node *root){ if (root->left!=NULL) inOrderTraversal(root->left); cout<<root->value<<", "; if (root->right!=NULL) inOrderTraversal(root->right); } void preOrderTraversal(Node *root){ cout<<root->value<<", "; if (root->left!=NULL) preOrderTraversal(root->left); if (root->right!=NULL) preOrderTraversal(root->right); } void postOrderTraversal(Node *root){ if (root->left!=NULL) postOrderTraversal(root->left); if (root->right!=NULL) postOrderTraversal(root->right); cout<<root->value<<", "; } void inOrderTraversalNoRecurse(Node *root){ Node *currNode = root; stack<Node*> myStack; while ( currNode!=NULL || !myStack.empty()){ if( currNode !=NULL){ myStack.push(currNode); currNode = currNode->left; } else{ currNode = myStack.top();myStack.pop(); cout<<currNode->value<<", "; currNode = currNode->right; } } } void preOrderTraversalNoRecurse(Node *root){ Node *currNode = root; stack<Node*> myStack; while ( currNode!=NULL || !myStack.empty()){ if( currNode !=NULL){ cout<<currNode->value<<", "; myStack.push(currNode->right); currNode = currNode->left; } else{ currNode = myStack.top();myStack.pop(); } } } void postOrderTraversalNoRecurse(Node *root){ Node *currNode = root; Node *lastVisited = NULL; Node *stackTop = NULL; stack<Node*> myStack; while ( currNode!=NULL || !myStack.empty()){ if( currNode !=NULL){ myStack.push(currNode); currNode = currNode->left; } else{ stackTop = myStack.top(); if (stackTop->right != NULL && stackTop->right != lastVisited) currNode = stackTop->right; else{ cout<<stackTop->value<<", "; myStack.pop(); lastVisited = stackTop; } } } } int main(){ Node *root = new Node; root->value = 1; root->left = new Node; root->right = new Node; root->left->value = 2; root->right->value = 3; root->left->left = new Node; root->left->right = new Node; root->right->left = new Node; root->right->right = new Node; root->left->left->value = 4; root->left->right->value = 5; root->right->left->value = 6; root->right->right->value = 7; cout<<"In order traversal with recursion:"<<endl; inOrderTraversal(root);cout<<endl; cout<<"In order traversal without recursion:"<<endl; inOrderTraversalNoRecurse(root);cout<<endl<<endl; cout<<"Pre order traversal with recursion:"<<endl; preOrderTraversal(root);cout<<endl; cout<<"Pre order traversal without recursion:"<<endl; preOrderTraversalNoRecurse(root);cout<<endl<<endl; cout<<"Post order traversal with recursion:"<<endl; postOrderTraversal(root);cout<<endl; cout<<"Post order traversal without recursion:"<<endl; postOrderTraversalNoRecurse(root);cout<<endl; } |

## Leave a Reply