## Saturday, October 5, 2013

### Binary Tree Post-Order Traversal - Recursive and Iterative Solution

Consider the tree:

To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Recursive solution

```postorder(Node *root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("Value : [%d]", root->value);
}
}```

Iterative solution
Iterative solution involves 2 stacks. So if we want to do the same thing iteratively; we just need to maintain 2 stacks child and parent. Following 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.

Here is the code 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();
}
}
```

Dry running the code
Lets see a light example of how it works. Suppose we have a binary tree as shown below 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}

Here is how the stack grows:

Iterative solution using arrays
```void iterativePostorder(node *root) {
struct   {
node *node;
unsigned vleft :1;   // Visited left?
unsigned vright :1;  // Visited right?
}save[100];

int top = 0;
save[top++].node = root;

while ( top != 0 )   {
/* Move to the left subtree if present and not visited */
if(root->left != NULL && !save[top].vleft)       {
save[top].vleft = 1;
save[top++].node = root;
root = root->left;
continue;
}       /* Move to the right subtree if present and not visited */
if(root->right != NULL && !save[top].vright )       {
save[top].vright = 1;
save[top++].node = root;
root = root->right;
continue;
}
printf("[%d] ", root->value);
/* Clean up the stack */
save[top].vleft = 0;
save[top].vright = 0;
/* Move up */
root = save[--top].node;
}
}```

http://leetcode.com/2010/10/binary-tree-post-order-traversal.html