Postorder traversal without recursion

Postorder traversal without recursion

We discussed inorder traversal without recursion and preorder traversals without recursion earlier. Now let’s focus on postorder traversal without recursion, which is most complex of three tree traversals. In post order traversal of binary tree, left and right children are visited before parent node. For example, post order traversal of below tree is :3,8,6,11,17,15,10

postorder traversal without recursion

Before continuing discussion on non-recursive implementation of post order traversal, understand how is it implemented with recursion.

Postorder traversal Recursive implementation

void postorder(Node *root){
     if(root){
          postorder(root->left);
          postorder(root->right);
          printf("%d", root->data);
     }
}

Looking at code, it is clear that parent node is visited twice, once coming up from left sub tree and second time when coming up from right sub tree. However, parent node is to be printed when we have already printed left as well as right child. So, we need to keep track of the previous visited node.
There are tree values possible for previous node:
1. Previous node is parent of current node, that means we are traversing tree downwards.  No need to do anything with the current node.
2. Previous node is left child of current node, that means we have already visited left child, but still not have visited right child, hence we move to right child of current node.
3. Previous node is right child of current node, left and right child of current node are already visited, hence all we need to do is to print current node.

Postorder traversal without recursion algorithm

1.Start with the root node and push the node onto stack.
2 Repeat all steps till stack is not empty. 
3.Peek the top of the stack. 
  3.1 If previous node is parent of current node : ( When we are moving down the tree)
    3.1.1 If left child is present, push left child onto stack. 
    3.1.2 Else if right child is present, push right child onto stack
    3.1.3 If left and right children are not present, print the node. 
  3.2 If previous node is left child of current node ( When moving up after visiting left node)
    3.2.1 If right child is not present, print current node
    3,2.2 If right child is present, push it onto stack. 
  3.3 If previous node is right child of current node ( When moving up after visiting right child )
    3.3.1 Print the node. 
    3.3.2 Pop node from stack.

Below figure explains execution of postorder traversal algorithm

postorder traversal without recursion implementationpostorder traversal without recursion

Postorder traversal without recursive implementation

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
#define STACK_SIZE 10
 
typedef struct stack{
        int top;
        Node *items[STACK_SIZE];
}stack;
 
void push(stack *ms, Node *item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}
 
Node * pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}
Node * peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}
 
void postorderTraversalWithoutStack(Node *root){
    stack ms;
    ms.top = -1;

    if(!root) return ;
 
    Node *currentNode = NULL ;
    push(&ms,root);
    Node *prev = NULL;
 
    while(!isEmpty(ms)){
        currentNode = peek(ms);
        /* case 1. We are moving down the tree. */
        if(!prev || prev->left == currentNode || prev->right == currentNode){
			if(currentNode->left)
				push(&ms,currentNode->left);
			else if(currentNode->right)
				push(&ms,currentNode->right);
			else {
                /* If node is leaf node */
                printf("%d ", currentNode->value);
                pop(&ms);
            }
        }
         /* case 2. We are moving up the tree from left child */
        if(currentNode->left == prev){
            if(currentNode->right)
                push(&ms,currentNode->right);
            else {
                printf("%d ", currentNode->value);
                pop(&ms);
            }
         }
 
        /* case 3. We are moving up the tree from right child */
         if(currentNode->right == prev){
              printf("%d ", currentNode->value);
              pop(&ms);
         }
         prev = currentNode;
      }
 
}
 
void postorder (Node * root){
	if ( !root ) return;
 
	postorder(root->left);
	postorder(root->right);
	printf("%d ", root->value );
}
 
Node * createNode(int value){
    Node * newNode =  (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;

    return newNode;
}

Node * addNode(Node *node, int value){
    if(!node){
    	return createNode(value);
    }
    else{
    	if (node->value > value){
    		node->left = addNode(node->left, value);
    	}
    	else{
    		node->right = addNode(node->right, value);
    	}
    }
    return node;
}
 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
        postorder(root);
        printf("\n");
        postorderTraversalWithoutStack(root);
        return 0;
}

Complexity of postorder traversal of binary search tree is O(n) because each node of tree is visited at least one.
Please share if there is something is wrong or missing. If you are interested in contributing to website or an interview experience to share, please contact us.