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