Iterative Postorder Traversal | Set 2 (Using One Stack)

Last Updated on December 14, 2022 by Prepbytes

Problem Statement:

You are given a binary tree. Your task is to print the postorder traversal of the binary tree using just 1 stack.

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 a 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 1 Stack)

We know that the postorder traversal is “left-right root”. This means that we have to try to go to the left of the given tree till it is possible. Then, we have to traverse the right of the tree till it is possible. After traversing both left and right, we have to print. So, the algorithm that we are going to use depends highly on our attempts to maintain the “left-right root” order.

Let us see what the algorithm is.

Algorithm:

1. Assign a variable current to the root of the tree and initialize a stack of nodes (initially empty).
2. While current does not become null OR the stack is not empty
   a. If the current is not equal to null
   i. Push current into the stack.
   ii. Move current to its left.
   b. Else
   • Assign a variable temp to the right child at the top of the stack.
   • So, the top of the stack might or might not have the right child. So, if the temp is null
     1. temp = stack.top()
     2. stack.pop()
     3. Add temp to the postorder
     4. While the stack is not empty AND the temp variable is equal to the right child of the top of the stack,
        a. temp = stack.top()
        b. stack.pop()
        c. Add temp to the postorder
        iii. Else, current = temp.

So, this algorithm helps maintain the postorder i.e. “left-right root”. Let us see an example dry run for the above algorithm.

Dry Run

Consider the following tree shown below.

So, we will start by having the variable curr (current) at the root of the tree.

So, according to the first step of the algorithm, since current is not equal to null, we add it to the stack and move it to its left.

We keep on repeating this step as shown below.

So, the value of current is now null as after pushing 30 into the stack, it moved to its left child which is null. Now, we follow the else condition in the algorithm. So, we will take a variable temp that will be the right child of the top of the stack. Since the top of the stack is 30, temp = right child of 30 i.e. 40.

Since a temp is not equal to null, current will now move to temp.

Since the current is now not null, we add it to the stack and move to its left child.

So, we see that again, the steps will be repeated. This means that every time, we try to go to the left child of every node and if the left is null, we move to its right. This will keep happening till we reach Node 60.

Now, the temp will be the right of the top of the stack. This means the temp will be the right of 60. So, temp = null.

Since temp = null, we pop a value from the stack and it becomes temp and we also add it to the postorder.

Now, while the stack is not empty AND temp is equal to the right child of the top of the stack, we have to keep popping from the stack and adding the node to the post order.

So, 50 was popped and added to the postorder. Now, we will pop 40 since the right child of 40 is equal to temp.

This will continue as shown below.

Now the right child of the top of the stack is null but temp = 30 (Node 30 not value). So, again, we see that curr = null and we follow the above-discussed steps.
You can complete the rest of the traversal yourself and you will find that we end up having the postorder of the tree correctly.

So, now that we have understood the procedure, let us write the code for the same.

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

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

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

vector<int> postOrderIterative(struct Node* root)
{
	vector<int> postOrderList;
	if (root == NULL)
		return postOrderList;

    stack<Node*> stk;
	stk.push(root);
	Node* prev = NULL;
	while (!stk.empty()) {
		auto current = stk.top();
		
        if (prev == NULL || prev->left == current
			|| prev->right == current) {
			if (current->left)
				stk.push(current->left);
			else if (current->right)
				stk.push(current->right);
			else {
				stk.pop();
				postOrderList.push_back(current->data);
			}
		}

		else if (current->left == prev) {
			if (current->right)
				stk.push(current->right);
			else {
				stk.pop();
				postOrderList.push_back(current->data);
			}

					}
		else if (current->right == prev) {
			stk.pop();
			postOrderList.push_back(current->data);
		}
		prev = current;
	}
	return postOrderList;
}

int main()
{
	
	struct Node* root = NULL;
    root = newNode(10);
	  root->left = newNode(20);
    root->left->left = newNode(30);
    root->left->left->right = newNode(40);
    root->left->left->right->right = newNode(50);
    root->left->left->right->right->right = newNode(60);
    root->right = newNode(70);
    root->right->left = newNode(80);
    
	printf("Post order traversal of binary tree is :\n");
	printf("[");
	vector<int> postOrderList = postOrderIterative(root);
	for (auto it : postOrderList)
		cout << it << " ";
	printf("]");
	return 0;
}

import java.util.ArrayList;
import java.util.Stack;


class Node {
	int data;
	Node left, right;

	Node(int item)
	{
		data = item;
		left = right;
	}
}

class BinaryTree {
	Node root;
	ArrayList<Integer> list = new ArrayList<Integer>();

	ArrayList<Integer> postOrderIterative(Node node)
	{
		Stack<Node> stk = new Stack<Node>();

		// Check for empty tree
		if (node == null)
			return list;
        
		stk.push(node);
		Node prev = null;
		while (!stk.isEmpty()) {
			Node current = stk.peek();

			if (prev == null || prev.left == current || prev.right == current) {
				if (current.left != null)
					stk.push(current.left);
				else if (current.right != null)
					stk.push(current.right);
				else {
					stk.pop();
					list.add(current.data);
				}

			}
			else if (current.left == prev) {
				if (current.right != null)
					stk.push(current.right);
				else {
					stk.pop();
					list.add(current.data);
				}

			}
			else if (current.right == prev) {
				stk.pop();
				list.add(current.data);
			}

			prev = current;
		}

		return list;
	}

	public static void main(String args[])
	{
		BinaryTree tree = new BinaryTree();

		// Let us create trees shown in above diagram
		tree.root = new Node(10);
		tree.root.left = new Node(20);
        tree.root.left.left = new Node(30);
        tree.root.left.left.right = new Node(40);
        tree.root.left.left.right.right = new Node(50);
        tree.root.left.left.right.right.right = new Node(60);
        tree.root.right = new Node(70);
        tree.root.right.left = new Node(80);

		ArrayList<Integer> mylist = tree.postOrderIterative(tree.root);

		System.out.println(
			"Post order traversal of binary tree is :");
		System.out.println(mylist);
	}
}

Time Complexity: The time complexity of this procedure is O(N) as we have to push and pop elements from the stack and the maximum height of the stack can be O(N).

Space Complexity: The space complexity of this procedure is O(N) as we are using a Stack to perform our operation.

We tried to discuss Iterative Postorder Traversal. We hope this article gives you a better understanding of Iterative Postorder Traversal, PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNC’s. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.