Iterative Inorder Traversal of Binary Search Tree

A student from my undergrad college asked an innocent question to me on a facebook group to write an iterative implementation for In-Order Traversal of a Binary Search Tree. Of course I obliged and wrote up a code. However, I had never dug deeper into the properties of such traversals before and my observation was quite unexpected.

I was asked a question in the M.Tech. programme interview at NIT Durgapur about the significance of In-Order traversals of BSTs. I wasn't aware of any! So I gave a prompt reply, that it prints the elements in a sorted order. I was sure I was correct but the expression on their faces led me believing I was surely wrong! Oh well, I never did study theory before, so I guess my anguish was justified.

So, for my fellow junior, here's the code I promised:

/*
 * Iterative Inorder Traversal
 * by Rahul Ghose 
 * 09.08.2011 02:23:42
 */
 
#include 
#include 
 
using namespace std;
 
struct mytree {
        int data;
        struct mytree *left;
        struct mytree *right;
};
 
struct mytree* newNode(int data) { 
        struct mytree* node = new struct mytree;
        node->data = data; 
        node->left = NULL; 
        node->right = NULL;
        return node;
} 
 
struct mytree* insert(struct mytree* node, int data) { 
        if (node == NULL) { 
                return(newNode(data)); 
        }
        
        if (data <= node->data) node->left = insert(node->left, data); 
        else node->right = insert(node->right, data);
        return(node); 
}
 
int main() {
        struct mytree *tree = NULL;
        stack<pair<struct mytree*,bool> > s;
 
        tree = insert(tree,20);
        tree = insert(tree, 5);
        tree = insert(tree,29);
        tree = insert(tree,15);
        tree = insert(tree, 4);
        tree = insert(tree,21);
        tree = insert(tree,32);
 
        s.push(make_pair(tree,false));
 
        while(!s.empty()) {
                pair<struct mytree*,bool> pp = s.top();
                struct mytree *t = pp.first;
                if(pp.second) { // marked
                        printf( "%d ", t->data );
                        s.pop();
                        if( t->right ) {
                                s.push( make_pair(t->right,false));
                        }
                        continue;
                }
                if(t->left) {
                        s.pop();
                        s.push(make_pair(t,true));      // mark for deletion
                        s.push(make_pair(t->left,false));
                }
                else {
                        printf( "%d ", t->data );
                        s.pop();
                        if( t->right ) {
                                s.push( make_pair(t->right,false));
                        }
                }
        }
 
 
        return 0;
}

Also on ideone : http://ideone.com/t118h