The postorder traversal is one of the traversing techniques used for visiting the node in the tree. It follows the principle LRN (Left-right-node). The following are the steps used for the postorder traversal:
- Traverse the left subtree by calling the postorder function recursively.
- Traverse the right subtree by calling the postorder function recursively.
- Access the data part of the current node.
Pseudocode of postorder traversal.
void postorder(root *r)
{
if(r== NULL)
then return;
else
postorder(r->left);
postorder(r->right);
print r->data;
In the above pseudo-code, we have defined a postorder function in which we added the logic of postorder traversal. As we already know that in postorder traversal, we first traverse the left subtree, then the right subtree and finally visit the root node. In the above code, we first have checked whether the value of root is NULL or not. If the value of root is NULL, then the control comes out of the function using the return statement. The 'if' condition is not satisfied, then the else part will be executed.
Implementation of Postorder traversal in C.
#include<stdio.h>
// Creating a node structure
struct node
{
int data;
struct node *left, *right;
};
// Creating a tree..
struct node* create()
{
struct node *temp;
int data;
temp = (struct node *)malloc(sizeof(struct node)); // creating a new node
printf("\nEnter the data: ");
scanf("%d", &data);
if(data==-1)
{
return NULL;
}
temp->data = data;
printf("\nEnter the left child of %d", data);
temp->left = create(); // creating a left child
printf("\nEnter the right child of %d", data);
temp->right = create(); // creating a right child
return temp;
}
//Postorder traversal
void postorder(struct node *root)
{
if(root==NULL)
return;
else
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
void main()
{
struct node *root;
root = create(); // calling create function.
postorder(root); // calling postorder function
}
Output
Iterative Postorder traversal
The above method that we have used for the Postorder traversal was the Recursion method. As we know that the recursion relies on the system stack, and if we want to convert the recursion into an iterative method, we need to use the external stack. There are two ways of iterative postorder traversal:
- Iterative postorder traversal using two stacks.
- Iterative postorder traversal using one stack
Iterative Postorder traversal using two stacks
We can also implement the Postorder traversal using two stacks. The idea behind this is to obtain the reversed postorder elements in the stack and then we pop the element one by one from the stack as the stack follows the LIFO principle. The question arises that how can we obtain the reversed order of the postorder elements. The solution to this problem can be obtained by using two stacks. The second stack is used to get the reversed order of the postorder elements.
The following are the steps used to implement postorder using two stacks:
- First, we will push the root to the stack.
- Secondly, we will create a while loop that runs till the first stack is not empty
- We pop a node from the first stack and push it into the second stack.
- We push the left and right child of a popped node to the first stack.
- We will print the data of the second stack.
Let's understand the postorder traversal using two stacks through an example.
Consider the below tree for the Postorder traversal.
So, let us consider two stacks and the tree as shown below.
The initial step is to push the root of the tree into Stack 1. Now, we will follow the following algorithm.
while(!stack1.empty())
curr=top of stack1
pop from stack1
push curr on stack2
if(curr -> left != NULL)
push curr -> left on stack1
if(curr -> right !=NULL)
push curr -> right on stack1So, according to the above algorithm, since Stack 1 is not empty, we pop it and push the element into Stack 2.
Now, the current node i.e. Node 1 has both left and right children. So, push the left child into Stack 1 first and then push the right child too.
Now, we pop Node 3 from Stack 1 and push it into Stack 2. We also add the left and right children of Node 3 to Stack 1.
Since Node 7 does not have any children, it just gets popped from Stack 1 and gets added to Stack 2.
Now, we pop Node 6 from Stack 1, push it into Stack 2, and push its right child Node 9 into Stack 1.
Now, Node 9 gets popped from Stack 1 and gets pushed into Stack 2.
Now we pop Node 2 from Stack 1 and push it into Stack 2. Also, the children of Node 2 i.e Node 4 and Node 5 get pushed into Stack 1.
Now, Node 5 will pop out from Stack 1 and push to Stack 2. Also, its child i.e. Node 8 will be pushed into Stack 1.
Now, Node 8 and Node 4 will be popped one by one from Stack 1 and pushed into Stack 2. Since they don’t have any children, Stack 1 will become empty.
So, now that Stack 1 is empty, we just have to pop all the elements from Stack 2 and as soon as an element is popped from Stack 2, we print it. Thus, we will get the postorder traversal.
Hence, we have completed the procedure.
Why did this work?
We wanted the order “left right root”. So, we pushed the order “root left right” into Stack 1. We popped the elements from Stack 1 and pushed them to Stack 2. Now, if we look carefully, on popping the elements from Stack 1, the order will be reversed of the order in which they were pushed i.e. the order will be “root right left” and this will be pushed into Stack 2 . This is because of the LIFO property of the stack.
Now, when we pop the elements from Stack 2, the order will reverse the order in which they were pushed. Since the elements were pushed in the order “root right left”, the order that we get on popping the elements from Stack 2 is “left right root”.
This is nothing but the postorder traversal.
So, this was the complete procedure of the iterative postorder traversal using 2 Stacks.
Algorithm of iterative postorder traversal (two stacks)
Step 1: Create two empty stacks named stack1 and stack2.
Step 2: Push the root node on stack1.
Step 3: TreeNode* current = NULL
Step 4: while(!stack1.empty())
current = top of stack1
pop current from stack1
Push current on stack1
if (current->left!= Null)
Push current->left on stack1
if(current->right!=NULL)
Push current->right on stack1
Step 5: while(!stack2.empty())
current = top of stack2
print current->value
pop current from the stack2
Iterative Postorder Traversal using one stack
In order to implement the Postorder traversal using one stack, first we need to move down till we reach the leftmost node. While moving down to the tree, we need to push the root and then right child of the root into the stack. When we reach the leftmost node having no right child, we need to print the node. If the leftmost node has a right child, we have to update the root so that the right child can be traversed before.
We have to perform three operations:
- If we are moving down the tree, push operation is performed.
- If we are coming up from the left-side, peek operation is performed
- If we are coming from the right-side, pop operation is performed
Let's understand through an example.
Step 1: The right child of node 1 exists. Push node 3 to the stack and then 1 to the stack.
Stack: 3, 1
Step 2: The right child of node 2 exists. Push node 5 to the stack and then 2 to the stack.
Stack: 3, 1, 5, 2
Step 3: The node 4 has no right child, so it gets printed and the current node is set to Null.
Stack: 3, 1, 5, 2
Output: 4
Step 4: Now, peek operation will be performed on the node 2. Since the right child of node 2 is topmost element in the stack, i.e., 5. So, pop the element 5 from the stack.
Stack: 3, 1, 2
Step 5: The right child of node 2 is 5, so we push 5 into the stack.
Stack: 3, 1, 2, 5
Step 6: Since node 5 does not have a right child so pop 5 from the stack and print 5. The current node is now set to NULL.
Stack: 3, 1, 2
Output: 4, 5
Step 7: The current node is NULL. Since the right child of node 2 is not the topmost element in the stack, so we will pop element 2 from the stack and print 2. The current node is now set to NULL.
Stack: 3, 1
Output: 4, 5, 2
Step 8: The current node is NULL. Since the right child of node 1 is 3 so we will perform the peek operation on node 1 and pop 3 from the stack.
Stack: 1
Step 9: The right child of 1 is 3 so we will push element 3 in the stack.
Stack: 1, 3
Step 10: The node 3 has a left child, i.e., 6, so it gets printed and the right child of node 3, i.e., 7 is pushed into the stack.
Stack: 1, 3, 7
Output: 4, 5, 2, 6
Step 11: Since there is no right child of node 7, so pop 7 from the stack.
Stack: 1, 3
Output: 4, 5, 2, 6, 7
Step 12: Since the right child of node 3 is not the topmost element in the stack, so pop 3 from the stack.
Stack: 1
Output: 4, 5, 2, 6, 7, 3
Step 12: Since the right child of node 1 is not the topmost element in the stack, so Pop 1 from the stack.
Stack: empty
Output: 4, 5, 2, 6, 7, 3, 1
The above output generated is the Postorder traversal.
Algorithm of iterative postorder traversal (one stack)
Step 1: Create one empty stack.
Step 2: Set current_node = root
Step 3: while(current_node!=NULL)
Push current_node->right into the stack
Push current_node into the stack
Step 4: Pop an element from the stack and set it as a current node.
If the popped element has a right child and the right child is top element then remove the right child from the stack. Push the current node back to the stack.
Otherwise print the current node's data and set the current node as NULL.
Step 5: Repeat step 3 and step 4 till the stack is not empty.
0 Comments