Iterative Postorder Traversal of Binary tree
Introduction
Our today’s topic is Iterative Postorder Traversal of a Binary tree. If you are reading this article, you must be familiar with binary trees, which is the prerequisite for this topic. Let’s understand the difference of traversal between linear data structures and nonlinear data structures. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc.), which can only be traversed in one logical manner, trees can be traversed in various ways, which are:
Depth First Traversal: In depthfirst search (DFS), the search tree is deepened as much as possible before going to the next sibling.
 Preorder traversal ( Root Left Right )
 Inorder traversal ( Left Root Right )
 Postorder traversal ( Left Right Root )
BreadthFirst Traversal: In Breadthfirst search(BFS), the nodes are traversed in a levelwise order.
Although there is a possibility to perform a post order traversal of the binary tree recursively, in this article we’ll be exploring postorder traversal using the Iterative approach, which will use stacks to perform the traversal of the tree.
Before any further due, let’s get started:
What is a Postorder Traversal?
A binary tree postorder traversal is a method of listing all of the tree's leaves and nodes so that for each node, all of its left children come before all of its right children, which come before the node itself. In simple words, Postorder traversal is a binary tree traversal approach in which you visit the left subtree first, then the right subtree, and finally the root.
LeftSubtree > RightSubtree > Root 
Consider the following example of a binary tree traversal utilising the postorder.
Source: wikimedia
In the preceding example, because the leftmost node is A, it is visited first. Following that, since D is the root node of C and E, the nodes C and E will be visited before the D node. The B node is now the last one to be visited in the left subtree. Now, the left subtree is visited, and because the algorithm expects the root to be visited last, it moves to the right subtree and processes each node in the same manner as it did for the left subtree.
Now that you are familiar with postorder traversal let’s look at the approaches we can perform to traverse a binary tree. As we are attempting to traverse the tree iteratively, thus we’ll be needing an auxiliary stack to process each node.
Approaches
 Using two stacks: In this section, we’ll learn how twostacks can assist in traversing the binary tree.
 Using one stack: This is the more efficient approach to solving this problem. We have discussed this approach in another blog.
Method 1: Using two stacks
We can use two stacks to implement the Postorder traversal. The goal is to acquire the reversed postorder elements in the stack and then pop the elements one by one from the stack, as the stack adheres to the LIFO principle. The question of how to obtain the reversed order of the postorder items emerges. This problem's answer can be reached by combining two stacks. The second stack is utilised to obtain the postorder items in reverse order.
The steps for implementing postorder utilising two stacks are as follows:
1  We'll start by pushing the root to the top of the stack.
2  Second, we'll run a while loop that will keep running until the first stack becomes empty and process the below steps.
 A node from the first stack is popped and pushed into the second.
 Push the left and right child of the popped node to the first stack.
3  The data from the second stack will be printed.
Source: Algorithms@tutorial Horizon
Consider the above example, and let’s try to understand each step in detail before moving to the Implementation:
1. Push 1 to the first stack.
First stack: 1
Second stack: Empty
2. Pop 1 from the first stack and push it to the second stack.
Push left and right children of 1 to the first stack.
First stack: 2, 3
Second stack: 1
3. Pop 3 from the first stack and push it to the second stack.
Push the left child of 3 to the first stack.
First stack: 2, 6
Second stack: 1, 3
4. Pop 6 from the first stack and push it to the second stack.
First stack: 2
Second stack: 1, 3, 6
6. Pop 2 from the first stack and push it to the second stack.
Push left and right children of 2 to the first stack.
First stack: 4, 5
Second stack: 1, 3, 6, 2
7. Pop 5 from the first stack and push it to the second stack.
First stack: 4
Second stack: 1, 3, 6, 2, 5
8. Pop 4 from the first stack and push it to the second stack.
First stack: Empty
Second stack: 1, 3, 6, 2, 5, 4
The algorithm stops here since there are no more items in the first stack.
Observe that the contents of the second stack are in postorder fashion. Print them.
Algorithm
Step 1: Create two empty stacks > 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 stack2
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

Implementation in C++
Output
4 5 2 6 3 1 
Time Complexity: The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the while loops.
Space Complexity: The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the two stacks.
To know more about conceptual knowledge and the implementation of the code, watch this video tutorial.
Implementation in Java
// Java program for iterative post // order using two stacks
import java.util.*; public class IterativePostorder { // node has tree components > data , left child and right child static class node { int data; node left, right;
public node(int data) { this.data = data; } }
// using two stacks static Stack<node> s1, s2;
static void postOrderIterative(node root) { // Create two stacks s1 = new Stack<>(); s2 = new Stack<>();
if (root == null) return;
// push root to first stack s1.push(root);
// Run while first stack is not empty while (!s1.isEmpty()) { // Pop an item from s1 and push it to s2 node curr = s1.pop(); s2.push(curr);
// Push left and right children of // removed item to s1 if (curr.left != null) s1.push(curr.left); if (curr.right != null) s1.push(curr.right); }
// Print all elements of second stack while (!s2.isEmpty()) { node curr = s2.pop(); System.out.print(curr.data + " "); } } public static void main(String[] args) { // Construct the below figure /* 1 / \ / \ 2 3 / \ / / \ / 4 5 6 */
node root = null; root = new node(1); root.left = new node(2); root.right = new node(3); root.left.left = new node(4); root.left.right = new node(5); root.right.left = new node(6);
postOrderIterative(root); } }

Output
4 5 2 6 3 1 
Time Complexity: The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the while loops.
Space Complexity: The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the two stacks.
Now, you have understood the approach; it’s time to implement the code on your own in your favourite programming language on CodeStudio. Complete your turn until it’s too late.
Frequently asked questions
 When to use postorder traversal?
If you know you need to inspect all the leaves before any nodes, you choose postorder, so you don't waste time inspecting roots in search of leaves.
 What is meant by traversal?
Tree traversal is the process of visiting each node in a tree exactly once. If a search results in a visit to all the nodes, it is called a traversal.
 What is recursive and nonrecursive tree traversal?
Recursive traversals are easier to implement because you only have to worry about one node, and they use the stack to store the state for each call, making them faster.
However, nonrecursive functions require you to store a list of all nodes for each level, and they can be far more complex than recursive ones.
 How does postorder traversal work?
The root node is visited last in this traversal technique. This is accomplished by first traversing the left subtree, then the right subtree, and ultimately reaching the root node.
 What are the three common types of traversals?
Inorder
 leftsubtree > visit the root > rightsubtree
Preorder
 visit the root > leftsubtree > rightsubtree
Postorder
 leftsubtree > rightsubtree > visit the root
For example:
 inorder: {5 , 15 , 18 , 20 , 25 , 30 , 35 , 40 , 45 , 50 , 60}
 preorder: {30 , 20 , 15 , 5 , 18 , 25 , 40 , 35 , 50 , 45 , 60}
 postorder: {5 , 18 , 15 , 25 , 20 , 35 , 45 , 60 , 50 , 40 , 30}
Key takeaways
To summarize, we’ve covered the tree traversal iteratively using the postorder DFS based on LRR( Left right root) algorithm. The postfix expression of an expression tree can be obtained using postorder traversal. Moreover, postorder traversal is also used when there is a need to visit the child nodes before the Root node. Postorder traversal is complicated among all the other traversals but is efficiently utilized in computer science. Along with that, a tree can be deleted from leaf to Node by using the postorder traversal.
So, in this article, we looked at postorder traversal with two stacks; however, there is a more interesting and memoryfriendly way to traverse the tree with a single stack.
Continue reading the fantastic articles to improve your programming expertise in all areas.
Enroll in our toptier courses taught by the best faculty to unleash the potential of learning.
Happy Leaning Ninja!
Comments
No comments yet
Be the first to share what you think