Postorder iterative verbose

void postorder_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 == 1){ // tag = 2: Now we have OPERATED on this node in that we have add its children into the stack pair<BinaryTreeNode *, int> p0 = make_pair(curr, 2); s.push(p0); if (curr->right != nullptr){ // tag = 1: Discovered a brand new node but have not OPERATE on it yet pair<BinaryTreeNode *, int> p1 = make_pair(curr->right, 1); s.push(p1); } if (curr->left != nullptr){ pair<BinaryTreeNode *, int> p2 = make_pair(curr->left, 1); s.push(p2); } } else if (tag == 2){ // second time seen: we have come back from its children cout << curr->val << endl; } } }