{"id":9618,"date":"2022-09-13T12:11:04","date_gmt":"2022-09-13T12:11:04","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9618"},"modified":"2022-10-03T03:58:45","modified_gmt":"2022-10-03T03:58:45","slug":"iterative-postorder-traversal-set-1-using-two-stacks","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/iterative-postorder-traversal-set-1-using-two-stacks\/","title":{"rendered":"Iterative Postorder Traversal | Set 1 (Using Two Stacks)"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

You are given a binary tree<\/a>. Your task is to print the postorder traversal of the tree iteratively, using 2 stacks.<\/p>\n

Example<\/strong><\/p>\n

Consider the tree given below.<\/p>\n

\"\"<\/p>\n

The postorder traversal means that we have to travel the children of every node before visiting the node in the order \u201cleft right node\u201d. Hence, the postorder traversal of the given tree is shown below.<\/p>\n

\"\"<\/p>\n

So, let us now discuss the approach.<\/p>\n

What is Postorder Traversal?<\/h3>\n

Before we directly jump into the solution, let us first discuss in detail, what postorder traversal is. Consider the tree given below.<\/p>\n

\"\"<\/p>\n

We are currently at the root node of the tree. There are three different types of traversals. The preorder<\/strong> traversal says that we have to follow the order \u201croot left right<\/strong>\u201d. This means that as soon as we are at a node, we have to mark it visited. <\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

The images above show that as soon as we reach a node in our traversal, consider it visited. So, the complete preorder traversal is shown below.<\/p>\n

\"\"<\/p>\n

The inorder<\/strong> traversal has the order of \u201cleft root right<\/strong>\u201d. This means that first we explore the left subtree, then mark the current node as visited, and then visit the right subtree. This is shown below.<\/p>\n

\"\"<\/p>\n

Traversing till here, we have not marked any node visited as we kept on visiting the left node. Now, node 4 does not have any left node. So, we can say that we have traversed its left node. Now, the order is \u201cleft node right\u201d, so after visiting the left node, we have to mark the node visited. Hence, we mark node 4 as visited.<\/p>\n

\"\"<\/p>\n

Similarly, the entire tree is traversed.<\/p>\n

\"\"<\/p>\n

Now, the postorder<\/strong> traversal has the order \u201cleft right root<\/strong>\u201d. This means that we have to first traverse the left subtree completely, then traverse the right subtree completely, and at the last, we have to mark the current node visited.<\/p>\n

\"\"<\/p>\n

Till here, we have not visited any node because we kept on moving to the left node of every node. Now, at Node 4, we see that there is no left node. So, we can say that we have visited the left node. Also, there is no right node. Hence, we can say that we have visited the right node also. So, now we can mark the current node visited. So, Node 4 is the first node in the postorder traversal.<\/p>\n

\"\"<\/p>\n

We keep on moving further as shown below.<\/p>\n

\"\"<\/p>\n

At Node 8, we don\u2019t have any left or right nodes. Hence, we can say that we have visited the left and right nodes of Node 8. So, mark it visited as well.<\/p>\n

\"\"<\/p>\n

Now, we reach node 5 again. Here, we can see that we have visited the left subtree of 5. There is no right child for Node 5. Hence, we can say that we have visited both the children. So, let us include 5 in the postorder traversal too.<\/p>\n

\"\"<\/p>\n

When we are at Node 2, we have already visited the left subtree (Node 4) and the right subtree (starting from Node 5) as well. So, we can now mark Node 2 as visited.<\/p>\n

\"\"<\/p>\n

Similarly, you can complete the rest of the traversal as well. The complete postorder traversal of the tree is shown below.<\/p>\n

\"\"<\/p>\n

So, for better understanding, have a look at the image shown below.<\/p>\n

\"\"<\/p>\n

Whenever we are on the left of any node<\/strong> i.e. no child has been traversed yet, we say that we are in a pre-node<\/strong> region. Whenever we are in the middle of the left and right child of a node<\/strong> i.e. the left subtree has been traversed but the right subtree has not been traversed, we are in the in-node<\/strong> region. Similarly, whenever we are in the right of a node<\/strong> i.e. both its children have been traversed, we are in the post-node<\/strong> region.<\/p>\n

Now that we have a complete understanding of different tree traversals, let us approach our problem i.e. postorder traversal using 2 stacks.<\/p>\n

Approach (Using 2 Stacks)<\/h3>\n

We know that the postorder traversal is \u201cleft right root\u201d. Using 2 stacks, the basic idea is to get the reverse of the postorder into one stack so that when we pop all the elements from that stack, we get the postorder traversal due to the FILO (or LIFO) principle of the stack.<\/p>\n

So, what is the reverse of postorder? It is \u201croot right left\u201d. This is very similar to the preorder traversal. Only we have to visit the right child first, before visiting the left child.<\/p>\n

So, let us consider two stacks and the tree as shown below.<\/p>\n

\"\"<\/p>\n

The initial step is to push the root of the tree into Stack 1. Now, we will follow the following algorithm.<\/p>\n

while(!stack1.empty())\n    curr=top of stack1\n    pop from stack1\n    push curr on stack2\n    if(curr -> left != NULL)\n        push curr -> left on stack1\n    if(curr -> right !=NULL)\n        push curr -> right on stack1<\/code><\/pre>\n
So, according to the above algorithm, since Stack 1 is not empty, we pop it and push the element into Stack 2.<\/p>\n
\"\"<\/p>\n
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.<\/p>\n
\"\"<\/p>\n
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.<\/p>\n
\"\"<\/p>\n
Since Node 7 does not have any children, it just gets popped from Stack 1 and gets added to Stack 2.<\/p>\n
\"\"<\/p>\n
Now, we pop Node 6 from Stack 1, push it into Stack 2, and push its right child Node 9 into Stack 1.<\/p>\n
\"\"<\/p>\n
Now, Node 9 gets popped from Stack 1 and gets pushed into Stack 2.<\/p>\n
\"\"<\/p>\n
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.<\/p>\n
\"\"<\/p>\n
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.<\/p>\n
\"\"<\/p>\n
Now, Node 8 and Node 4 will be popped one by one from Stack 1 and pushed into Stack 2. Since they don\u2019t have any children, Stack 1 will become empty.<\/p>\n
\"\"<\/p>\n
\"\"<\/p>\n
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.<\/p>\n
\"\"<\/p>\n
Hence, we have completed the procedure.<\/p>\n
Why did this work?<\/strong><\/p>\n
We wanted the order \u201cleft right root<\/strong>\u201d. So, we pushed the order \u201croot left right<\/strong>\u201d into Stack 1<\/strong>. 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 \u201croot right left<\/strong>\u201d and this will be pushed into Stack 2<\/strong> . This is because of the LIFO property of the stack. <\/p>\n
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 \u201croot right left\u201d, the order that we get on popping the elements from Stack 2 is \u201cleft right root\u201d.<\/p>\n
This is nothing but the postorder traversal.<\/p>\n
So, this was the complete procedure of the iterative postorder traversal using 2 Stacks. Now that we have understood the complete procedure, let us write the code for the same.<\/p>\n\t\t\t\t\t\t