in_order_using_stack.cpp

/*
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack.
     b) Print the popped item, set current = popped_item->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
*/


void inOrder(struct Node *root)
{
    stack<Node *> s;
    Node *curr = root;
 
    while (curr != NULL || s.empty() == false)
    {
        // Reach the left most Node of the curr Node 
        while (curr !=  NULL)
        {
            //place pointer to a tree node on the stack before traversing the node's left subtree 
            s.push(curr);
            curr = curr->left;
        }
 
        //Current must be NULL at this point 
        curr = s.top();
        s.pop();
 
        cout << curr->data << " ";
 
        // we have visited the node and its left subtree.  Now, it's right subtree's turn 
        curr = curr->right;
 
    }
}