I feel you haven't asked the question properly. I will try to answer the question as to how one can think about implementing the iterative version of in-order traversal(I just happen to have given this some thought and implemented it very recently. I feel I will help myself too by putting this down) given that one knows the recursive version.
Each function call in a recursive version seeks to visit the node associated with the function call. The function is coded such that activation-frame corresponding to a node is saved onto the system stack(stack area of that process) before the it can do its main job, i.e. visit the node. This is so because we want to visit the left subtree of the node before visiting the node itself.
After the left subtree is visited, a return to the frame of our saved node results in the language environment popping the same from the internal stack and a visit to our node is now allowed.
We have to mimic this pushing and popping with an explicit stack.
template<class T>
void inorder(node<T> *root)
{
// The stack stores the parent nodes who have to be traversed after their
// left sub-tree has been traversed
stack<node<T>*> s;
// points to the currently processing node
node<T>* cur = root;
// Stack-not-empty implies that trees represented by nodes in the stack
// have their right sub-tree un-traversed
// cur-not-null implies that the tree represented by 'cur' has its root
// node and left sub-tree un-traversed
while (cur != NULL || !s.empty())
{
if (cur != NULL)
{
for (; cur->l != NULL; cur = cur->l) // traverse to the leftmost child because every other left child will have a left subtree
s.push(cur);
visit(cur); // visit him. At this point the left subtree and the parent is visited
cur = cur->r; // set course to visit the right sub-tree
}
else
{// the right sub-tree is empty. cur was set in the last iteration to the right subtree
node<T> *parent = s.top();
s.pop();
visit(parent);
cur = parent->r;
}
}
}
The best way to understand this is to draw the functioning of the internal stack on paper on each call and return of the recursive version.
