Python Algorithm – Iterative Postorder Traversal | Set 1 (Using Two Stacks)

We have discussed iterative inorder and iterative preorder traversals. In this post, iterative postorder traversal is discussed which is more complex than the other two traversals (due to its nature of non-tail recursion, there is an extra statement after the final recursive call to itself). The postorder traversal can easily be done using two stacks though. The idea is to push reverse postorder traversal to a stack. Once we have reverse postorder traversal in a stack, we can just pop all items one by one from the stack and print them, this order of printing will be in postorder because of LIFO property of stacks. Now the question is, how to get reverse post order elements in a stack – the other stack is used for this purpose. For example, in the following tree, we need to get 1, 3, 7, 6, 2, 5, 4 in a stack. If take a closer look at this sequence, we can observe that this sequence is very similar to preorder traversal. The only difference is right child is visited before left child and therefore sequence is “root right left” instead of “root left right”. So we can do something like iterative preorder traversal with following differences.
a) Instead of printing an item, we push it to a stack.
b) We push left subtree before right subtree.

Following is the complete algorithm. After step 2, we get reverse postorder traversal in second stack. We use first stack to get this order.

1. Push root to first stack.
2. Loop while first stack is not empty
   2.1 Pop a node from first stack and push it to second stack
   2.2 Push left and right children of the popped node to first stack
3. Print contents of second stack

Let us consider the following tree

Following are the steps to print postorder traversal of the above tree using two stacks.

1. Push 1 to first stack.
      First stack: 1
      Second stack: Empty

2. Pop 1 from first stack and push it to second stack. 
   Push left and right children of 1 to first stack
      First stack: 2, 3
      Second stack: 1

3. Pop 3 from first stack and push it to second stack. 
   Push left and right children of 3 to first stack
      First stack: 2, 6, 7
      Second stack:1, 3

4. Pop 7 from first stack and push it to second stack.
      First stack: 2, 6
      Second stack:1, 3, 7

5. Pop 6 from first stack and push it to second stack.
      First stack: 2
      Second stack:1, 3, 7, 6

6. Pop 2 from first stack and push it to second stack. 
   Push left and right children of 2 to first stack
      First stack: 4, 5
      Second stack:1, 3, 7, 6, 2

7. Pop 5 from first stack and push it to second stack.
      First stack: 4
      Second stack: 1, 3, 7, 6, 2, 5

8. Pop 4 from first stack and push it to second stack.
      First stack: Empty
      Second stack: 1, 3, 7, 6, 2, 5, 4

The algorithm stops since there is no more item in first stack. 
Observe that content of second stack is in postorder fashion. Print them.

Following is C implementation of iterative postorder traversal using two stacks.

Python Programming:

[pastacode lang=”python” manual=”%23%20Python%20porgram%20for%20iterative%20postorder%20traversal%20using%0A%23%20two%20stacks%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20An%20iterative%20function%20to%20do%20postorder%20traversal%20of%20a%0A%23%20given%20binary%20tree%0Adef%20postOrderIterative(root)%3A%20%0A%20%0A%20%20%20%20if%20root%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%0A%20%20%20%20%23%20Create%20two%20stacks%20%0A%20%20%20%20s1%20%3D%20%5B%5D%0A%20%20%20%20s2%20%3D%20%5B%5D%0A%20%20%20%20%20%0A%20%20%20%20%23%20Push%20root%20to%20first%20stack%0A%20%20%20%20s1.append(root)%0A%20%20%20%20%20%0A%20%20%20%20%23%20Run%20while%20first%20stack%20is%20not%20empty%0A%20%20%20%20while%20(len(s1)%20%3E0)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Pop%20an%20item%20from%20s1%20and%20append%20it%20to%20s2%0A%20%20%20%20%20%20%20%20node%20%3D%20s1.pop()%0A%20%20%20%20%20%20%20%20s2.append(node)%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Push%20left%20and%20right%20children%20of%20removed%20item%20to%20s1%0A%20%20%20%20%20%20%20%20if%20node.left%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20s1.append(node.left)%0A%20%20%20%20%20%20%20%20if%20node.right%20is%20not%20None%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20s1.append(node.right)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Print%20all%20eleements%20of%20second%20stack%0A%20%20%20%20while(len(s2)%20%3E%200)%3A%0A%20%20%20%20%20%20%20%20node%20%3D%20s2.pop()%0A%20%20%20%20%20%20%20%20print%20node.data%2C%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aroot%20%3D%20Node(1)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(3)%0Aroot.left.left%20%3D%20Node(4)%0Aroot.left.right%20%3D%20Node(5)%0Aroot.right.left%20%3D%20Node(6)%0Aroot.right.right%20%3D%20Node(7)%0ApostOrderIterative(root)” message=”” highlight=”” provider=”manual”/]

Output:

4 5 2 6 7 3 1

Following is overview of the above post.
Iterative preorder traversal can be easily implemented using two stacks. The first stack is used to get the reverse postorder traversal in second stack. The steps to get reverse postorder are similar to iterative preorder.