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

See also