Another good way of implementing iterative postorder.

Here is the subroutine for implementing iterative post order.

template

void BST::iterativePostorder() {

Stack*> travStack;

BSTNode* p = root, *q = root;

while (p != 0) {

for (;p->left != 0; p = p->left)

travStack.push(p);

while (p!=0 && (p->right == 0 || p->right == q)) {

visit(p);

q = p;

if (travStack.empty())

return;

p = travStack.pop();

}

travStack.push(p);

p = p->right;

}

}

Here q is used to remember the path we have come from. As it is a postorder a node needs to be visited when our right child is q.