We saw the iterative pre-order and post-order traversal of a binary tree. Here is now, one can find the in-order traversal of a binary tree.

Here are simple steps to do that:
Go to the non-traversed left-most node every time until nothing is left.
Print this, its parent and in-order of it right counter part.

Algorithm for doing this will be as follows:



1.Crusor &lt= root

2.While true

a.If cursor is not null; 

i.push in stack

ii.Cursor &lt= left child of cursor

b.end

c.If Cursor is NULL

i.Cursor &lt= top of stack

ii.Pop from stack and print

iii.Cursor &lt= Right child of cursor

d.end

3.end

Code:
inOrderTraversalIterative(BinaryTree *root)
{ 
    stack<BinaryTree*> s;

    cursor = root;                    //set cursor to root of binary tree
    done = false;

   while (!done)
   {
     if(cursor != NULL)
     {
        s.push(cursor);             //place pointer to node on the stack
                                    //before traversing the node's left subtree
        cursor = cursor->left();    //traverse the left subtree
     }
     else                        //backtrack from the empty subtree and
                                 //visit the node at the top of the stack;
                                 //however, if the stack is empty, you are
                                 //done
     {
        if (!s.empty())
        {
            cursor = s.top();
            s.pop();
            cout << cursor->data();
            cursor = cursor->right();
        }
        else
          done = true;
     }
  }
}


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.