Question: Find the post order traversal of a binary tree iteratively.

Answer: We have seen the recursive post order traversal of a Binary tree:

`void postOrderTraversal(TreeNode *root){  if (!root) return;  postOrderTraversal(root->left);  postOrderTraversal(root->right);  cout << root->data;}`

So if we want to do the same thing iteratively; we just need to maintain 2 stacks child and parent. Follwoing is the algorithm of this method:
• Push the root node to the child stack.
• while child stack is not empty
• Pop a node from the child stack, and push it to the parent stack.
• Push its left child followed by its right child to the child stack.
• end while
• Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.

Below is the C++ program for the same:
`void postOrderTraversalIterativeTwoStacks(TreeNode *root){    if (!root) return;    stack<BinaryTree*> child;    stack<BinaryTree*> parent;        //Initialization    child.push(root);        while (!child.empty()) {        BinaryTree *curr = child.top();        parent.push(curr);        child.pop();        if (curr->left)            child.push(curr->left);        if (curr->right)            child.push(curr->right);    }        //Printing the post order traversal       while (!parent.empty()) {                cout << parent.top()->data << " ";            parent.pop();    }}`

Lets see a light example of how it works. Suppose we have a binary tree as shown at the right side and we need to compute its post order traversal. It's post order traversal will be
{A, C, E, D, B, H, I, G, F}

Let see step-step-step how two stacks grow and contract in each iteration:

 Child Stack Parent Stack F NIL G B F I G B F I H G B F H I G B F B H I D G A F D B H E I C G A F E D B H I C G A F C E D B H I G A F A C E D B H I G NIL F