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 StackParent Stack
FNIL
G
BF
IG
BF
I
HG
BF
H
I
G
BF
B
H
I
DG
AF
D
B
H
EI
CG
AF
E
D
B
H
I
CG
AF
C
E
D
B
H
I
G
AF
A
C
E
D
B
H
I
G
NILF

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.