Morris Postorder Tree Traversal in C++

In this tutorial, we will learn Morris postorder tree traversal in C++. For learning morris postorder tree traversal first we should know about what is postorder tree traversal.

Postorder Tree Traversal:

It is a type of tree traversal in which first we visit Left subtree then Right Subtree and then the root of the graph.

Morris Postorder Tree Traversal in C++

Steps of Morris Postorder Tree Traversal algorithm:

1.  Make input tree left subtree of temp

2. Initialize curr to temp

3. If the left child of curr is NULL{

curr=curr->right

}

else{

make the left child of curr predecessor and find postorder predecessor

if the right child of the predecessor is NULL{

make curr as the right child of the predecessor

curr=curr->left

}

else{

reverse the right references from the predecessor to curr

visit all the nodes from the predecessor to curr again and reverse the right references from the predecessor to curr

remove reference between predecessor to curr

}

}

4. Repeat step 3 until curr is valid

Flow of Morris Postorder Tree Traversal

Input tree:

Input tree of Morris Postorder Tree Traversal

Iteration 1:

iteration 1 of Morris Postorder Tree Traversal in C++

Iteration 2:

2nd iteration of Morris Postorder Tree Traversal in C++

Iteration 3:

3rd iteration of Morris Postorder Tree Traversal in C++

Iteration 4:

4th iteration

Iteration 5:

5th iteration

Iteration 6:

6th iteration of Morris Postorder Tree Traversal in C++

Iteration 7:

7th iteration

Iteration 8:

iteration 8

Iteration 9:

9th iteration of Morris Postorder Tree Traversal in C++

Program to implement Morris Postorder Tree Traversal in C++

#include<iostream> 
using namespace std;

/* Each node of a tree contains 1 data field and 2 links, 1 link to left child and 1 link to right child */
/* Typedef function is used to assign an alternative name to the existing datatype. Here, using typedef function we can write 'struct Node' as just 'Node' */
typedef struct Node
{ 
  int data; 
  Node* left; 
  Node* right; 
}Node; 


Node* new_node(int );
void morris_postorder_traversal(Node*);

int main() 
{ 
  Node* root = new_node(1); 
  root->left = new_node(2); 
  root->right = new_node(5); 
  root->left->left = new_node(3); 
  root->left->right = new_node(4);
  /* this input tree is shown in above diagram */ 

  cout<<"\nMorris Postorder Traversal of the graph: ";
  morris_postorder_traversal(root);
  
  return 0; 
} 

/* This function is used to create new node with the given data */
Node* new_node(int data) 
{ 
  Node* node = new Node; 
  node->data = data; 
  node->left = NULL; 
  node->right = NULL; 
  return node; 
}

/* p may point to any arbitrary position after giving whole valid output and to avoid that we have used this function */
int is_nodevalid(Node* p)
{
  if(p->data==1 || p->data==2 || p->data==3 || p->data==4 || p->data==5 || p->left->data==1)
  return 1;
  
  return 0;
}

void morris_postorder_traversal(Node *root)
{
  Node *curr, *predecessor, *t1, *t2, *t3;
  Node *temp = new Node;
  
  /* make input tree left subtree of temp */
  temp->left = root;

  curr=temp;

  while(is_nodevalid(curr))
  {        
    	if(curr->left==NULL)
        {
       		curr=curr->right;
    	} 
    else
    {
      /* Finding postorder predecessor */
        	predecessor=curr->left;
        	while(predecessor->right!=NULL && predecessor->right != curr)
                {
           		predecessor=predecessor->right;
        	  }

        	if(predecessor->right == NULL)
                { 
            	   predecessor->right=curr;    
            	   curr=curr->left;
        	  }
      else 
      {                          

           		/* if predeccessor's right child is curr */
        /* reverse the right references from predecessor to curr */
            	t1=curr;
            	t2=curr->left;              
            	while(t2!=curr)
                {            
                	t3=t2->right;
                	t2->right=t1;
                	t1=t2;
                	t2=t3;
            	  }
            	
            	/* visit all the nodes from predecessor to curr again and reverse the right references from predecessor to curr */
            	t1=curr;
            	t2=predecessor;
            	while(t2!=curr)
                {

                	cout<<t2->data<<" ";  
                	t3=t2->right;          
                	t2->right=t1;
                	t1=t2;
                	t2=t3;
            	  }
            	
            	/* remove reference between predecessor to curr */
            	predecessor->right=NULL; 
            	curr=curr->right;
        	}
    	}
  }    
}

Output:

Morris Postorder Traversal of the graph: 3 4 2 5 1

Time Complexity & Space Complexity

The Time Complexity and Space Complexity of the program is O(n) and O(1) respectively.

 

You may also read:

  1. Morris Preorder Tree Traversal in C++
  2. Morris Inorder Tree Traversal in C++

Leave a Reply

Your email address will not be published. Required fields are marked *