Inorder Traversal Iterative Verbose

void inorder_iterative(BinaryTreeNode * root){ if (root == nullptr) return; // This version, all nodes pushed into the stack at least once stack< pair<BinaryTreeNode *, int> > s; pair<BinaryTreeNode *, int> p = make_pair(root, 1); // int = 1: first time see. int = 2: second time see s.push(p); while(!s.empty()){ p = s.top(); s.pop(); BinaryTreeNode * curr = p.first; int tag = p.second; if (tag == 2) // second time see: we come back from the children! cout << curr->val << endl; else{ // first time seen. Operate on this if (curr->right != nullptr){ pair<BinaryTreeNode *, int> p1 = make_pair(curr->right, 1); // right node s.push(p1); } pair<BinaryTreeNode *, int> p = make_pair(curr, 2); s.push(p); if (curr->left != nullptr){ pair<BinaryTreeNode *, int> p2 = make_pair(curr->left, 1); // left node s.push(p2); } } } }