Iterative Postorder Traversal | Set 1 (Using Two Stacks)

Last Updated on October 3, 2022 by Ria Pathak

Problem Statement

You are given a binary tree. Your task is to print the postorder traversal of the tree iteratively, using 2 stacks.

Example

Consider the tree given below.

The postorder traversal means that we have to travel the children of every node before visiting the node in the order “left right node”. Hence, the postorder traversal of the given tree is shown below.

So, let us now discuss the approach.

What is Postorder Traversal?

Before we directly jump into the solution, let us first discuss in detail, what postorder traversal is. Consider the tree given below.

We are currently at the root node of the tree. There are three different types of traversals. The preorder traversal says that we have to follow the order “root left right”. This means that as soon as we are at a node, we have to mark it visited.

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.

The inorder traversal has the order of “left root right”. 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.

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 “left node right”, so after visiting the left node, we have to mark the node visited. Hence, we mark node 4 as visited.

Similarly, the entire tree is traversed.

Now, the postorder traversal has the order “left right root”. 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.

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.

We keep on moving further as shown below.

At Node 8, we don’t 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.

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.

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.

Similarly, you can complete the rest of the traversal as well. The complete postorder traversal of the tree is shown below.

So, for better understanding, have a look at the image shown below.

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

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

Approach (Using 2 Stacks)

We know that the postorder traversal is “left right root”. 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.

So, what is the reverse of postorder? It is “root right left”. This is very similar to the preorder traversal. Only we have to visit the right child first, before visiting the left child.

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 stack1

So, 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. Now that we have understood the complete procedure, let us write the code for the same.

#include <bits/stdc++.h>
using namespace std;

//tree node 
struct Node {

	int data;
	Node *left, *right;
};


Node* newNode(int data)
{
	Node* node = new Node;
	node->data = data;
	node->left = node->right = NULL;
	return node;
}

void post_order_iterative(Node* root)
{
	if (root == NULL)
		return;
		
	stack<Node *> s1, s2;

	
	s1.push(root);
	Node* node;

	
	while (!s1.empty()) {
		
		//pop from stack 1 and add the elemnt to stack 2
		node = s1.top();
		s1.pop();
		s2.push(node);

		//add children to stack 1
		if (node->left)
			s1.push(node->left);
		if (node->right)
			s1.push(node->right);
	}

	// Print all elements of second stack -> this is postorder traversal
	while (!s2.empty()) {
		node = s2.top();
		s2.pop();
		cout << node->data << " ";
	}
}

int main()
{
	//The tree that we have been discussing so far
	Node* root = NULL;
	root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
    root->left->right->left = newNode(8);
    root->right->left->right = newNode(9);

	post_order_iterative(root);

	return 0;
}

import java.util.*;
public class Main {

	static class node {
		int data;
		node left, right;

		public node(int data)
		{
			this.data = data;
		}
	}

	static Stack<node> s1, s2;

	static void postOrderIterative(node root)
	{
		s1 = new Stack<>();
		s2 = new Stack<>();

		if (root == null)
			return;

		// push root to first stack
		s1.push(root);

		while (!s1.isEmpty()) {
			// Pop an item from stack 1 and push it to stack 2
			node temp = s1.pop();
			s2.push(temp);

            //add children of current node to stack 1
			if (temp.left != null)
				s1.push(temp.left);
			if (temp.right != null)
				s1.push(temp.right);
		}

		// Print all elements of second stack -> this is the postorder traversal
		while (!s2.isEmpty()) {
			node temp = s2.pop();
			System.out.print(temp.data + " ");
		}
	}

	public static void main(String[] args)
	{   
	    //tree that we have been discussing so far
		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);
		root.right.right = new node(7);
		root.left.right.left = new node(8);
        root.right.left.right = new node(9);
		

		postOrderIterative(root);
	}
}

Time Complexity

The time complexity of this procedure is O(N) where N is the number of nodes in the tree. This is because we have to traverse all the nodes of the tree once in order to print them.

Space Complexity

The space complexity of this approach is O(N). This is because we are using 2 stacks and Stack 2 at the end contains all the N nodes of the tree.

This article tried to discuss Iterative Postorder Traversal. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.