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

Read More

Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

In order to illustrate the 3 traversals  - pre order, in-order and post-order lets take following tree:

Preorder traversal:
To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Implementing pre-order traversal

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

More details here.


Inorder traversal:
Inorder traversal prints the binary tree in increasing order. To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Consider the tree below

Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Implementing inorder traversal(recursive)

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

More details here.  

Postorder traversal:
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.

Consider the tree below

Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Implementing post order traversal

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

More details here.
Time complexity of above traversals is O(n).

BFS-Breadth first search
This is same as level order traversal, where we go level by level of the tree.

more details here.

DFS - Depth first search
more details here.

Level order traversal

Zig-zag order traversal

more details here.

Read More