Postorder Traversal without Recursion

Problem Statement

Given a tree, we need to traverse the tree in a post-order traversal way and print the nodes of the tree in the post-order traversal order. The traversal should be done without using recursion.

In order to proceed with the problem, we need to understand how post-order traversal is done over the tree.

How is Post Order Traversal Done?

In post-order traversal without recursion, traversal is done in the following order :

• Firstly, the left subtree is visited.
• Secondly, the right subtree is visited.
• And lastly the root is visited.

As trees are nonlinear data structures so the traversal is not similar to linear data structures like arrays, linked lists, etc. In a binary tree, there can be more than one next node from the current node of the tree.

Let's see with an Example how post-order traversal is done.

Example

Let's represent a tree and do post-order traversal on it.

The output of the post-order traversal

Let's understand in steps how the post-order traversal is done in the above tree example.

Example Explanation

Let's understand how post-order traversal is done using two stacks by traversing on the tree shown below. Following are the steps are taken to get post order traversal in the tree

• push 15 to the first stack First stack - 15 Second stack - Empty

• pop 15 from the first stack and push it to the second stack and then push left and right child of 15 to the first stack First stack - 10 23 Second stack - 15

• pop top node from first stack i.e 23 and push it to second stack and then push its left and right node to first stack First stack - 10 9 17 Second stack - 15 23

• pop top node from first stack i.e 17 and push it to second stack and then push its left and right node to first stack. If it does not have a left or right child then don't push anything to the second stack. First stack - 10 9 Second stack - 15 23 17

• pop top node from first stack i.e 9 and push it to second stack and then push its left and right node to first stack. If it does not have a left or right child then don't push anything to the second stack. First stack - 10 Second stack - 15 23 17 9

• pop top node from first stack i.e 10 and push it to second stack and then push its left and right node to first stack. If it does not have a left or right child then don't push anything to the second stack. First stack - 5 2 Second stack - 15 23 17 9 10

• pop top node from first stack i.e 2 and push it to second stack and then push its left and right node to first stack. If it does not have a left or right child then don't push anything to the second stack. First stack - 5 Second stack - 15 23 17 9 10 2

• pop top node from first stack i.e 2 and push it to second stack and then push its left and right node to first stack. If it does not have a left or right child then don't push anything to the second stack. First stack - Empty Second stack - 15 23 17 9 10 2 5

• If the first stack becomes empty then pop the nodes of the second stack which will give the post-order traversal.

• Result - 5 2 10 9 17 23 15

Input/Output

Input

Output

Constraints

The constraint for post-order traversal without recursion are :

• 1 <= number of nodes <= 10^5
• -10^9 <= node value <= 10^9

Algorithm 1- Iterative Approach - Using Two Stacks

Algorithm

In this algorithm, we use two stacks to store the nodes of the binary tree. Let's see how the algorithm works:

• Start from the root node and push the root node to the first stack
• While the first stack is not empty repeat the below two steps

1. From the first stack pop a node and push that node to the second stack
2. If there is a left and right node of the popped stack then push the left and right node of the popped stack to the first stack

• Once the first stack is empty print the nodes in the second stack. It will be post-order traversal order.

Implementation in C++

Implementation in Java

Implementation in Python

Output

• Time Complexity: As in the post-order traversal every node is iterated and pushed to the stack so the time taken to do traversal on every node of the tree is O(n), where n is the number of nodes in the tree.
• Space Complexity: The extra space used in the post-order traversal of the two stacks. In the worst case, the stack will contain all the nodes of the stack so the size of the stack should be equal to the number of nodes in the tree. So, space complexity = O(n), where n is the number of nodes in the tree.

Algorithm 2- Iterative Approach - Using One Stack

Algorithm: In this method, we will reduce the space complexity from two stacks to one stack. Let's see how the algorithm works in steps :

• Create an empty stack
• Repeat the below steps while the root is not NULL
  1. Push the right root child and then push the root node.
  2. Set root as root's left child.
• pop the node from the stack and set it as the root node
  1. If popped node has a right child and the right child node is present at the top of the stack then pop the right child node and push the root node to the stack and set root as the root's right child
  2. Else print the root node and set the root to NULL.
• Repeat the above two steps until the stack is not empty.

Implementation in C++ :

Implementation in Java

Implementation in Python

Output

• Time complexity : The traversal is done iteratively over all the nodes of the tree so, the time taken to do traversal on each and every node is O(n), where n is the number of nodes in the tree.
• Space complexity : The algorithm uses only single stack which can store all the nodes in the worst case. so, the space required in this algorithm is O(n).

Algorithm 3- Iterative Approach - Using Stack and Hashing

Algorithm: In this method, we will use stack and unordered map for hashing. Let's understand the step-by-step algorithm.

• Create an unordered map for marking the visited nodes while traversing and create a stack to find the post-order traversal.
• Firstly, push the root node in the stack and then repeat the below steps until the stack is not empty.
• Mark the current node(node on top of stack) as visited in the hash table.
• Check if the left child of the current node is not Null, if yes then push the left child node to the stack.
• If a left child is not present check for the right child. If the right child is present then push it to the stack.
• If the current node has no left or right child node then simply pop the node from the stack and store it in the result list.
• As the stack gets empty the nodes in our result list will give the post-order traversal.

Implementation in C++ :

Implementation in Java

Implementation in Python

Output

Time complexity : As in this algorithm we are traversing over each node of the tree and then marking it visited in the hashmap. So, the time required to traverse all the nodes of the tree will be O(n) Space complexity : Extra space of the stack and hashmap is used to store the nodes and mark visited nodes so the space complexity of the algorithm will be O(n)

Algorithm 4- Using No Stacks (Morris Traversal)

In this algorithm we will not use any extra space for post order traversal. Lets understand this algorithm.

Instead of using stacks to remember our way back up the tree, we are going to modify the tree to create upwards links. The idea is based on Threaded Binary Tree. The diagonal d1, d2,d3, and d4 shown in the figure above are first reversed, then printed, and then re-reversed.

We reverse each diagonal shown in the picture (d1-d4), print it, and re-reverse it.

• Create a temp or dummy node and make the left node of the temp node point to the root node of the tree.
• Set the dummy node as the root node.
• Repeat till root is not null.
  1. If the root has a left child node then find the inorder predecessor i.e. rightmost node of its left node. Then make it point to root.
  2. If it is already pointing to the root i.e it is already traversed then reverse the direction from left to the root node and print the nodes.
• If a left child is null do the same above steps with the right child.

Implementation in C++

Implementation in Java

Implementation in Python

Output

Time complexity : As in morris algorithm we traverse each and every node of the tree for checking the conditions of morris traversal. The time complexity of the algorithm is O(N) Space complexity : Since we use a vector to store the post order traversal of the Tree, the sapce complexity of the algorithm is O(N)