Binary Tree-Postorder Traversal – Non Recursive Approach

Objective: Given a binary tree, write a non recursive or iterative algorithm for postorder traversal.

Tree Traversals - Postorder
Tree Traversals – Postorder

Example:

Earlier we have seen “What is postorder traversal and recursive algorithm for it“, In this article we will solve it with iterative/Non Recursive manner.

Approach:

  • We have seen how we do inorder and preorder traversals without recursion using Stack, But post order traversal will be different and slightly more complex than other two. Reason is post order is non-tail recursive ( The statements execute after the recursive call).
  • If you just observe here, postorder traversal is just reverse of preorder traversal (1 3 7 6 2 5 4 if we traverse the right node first and then left node.)
  • So idea is follow the same technique as preorder traversal and instead of printing it push it to the another Stack so that they will come out in reverse order (LIFO).
  • At the end just pop all the items from the second Stack and print it.

Pseudo Code:

  1. Push root into Stack_One.
  2. while(Stack_One is not empty)
    1. Pop the node from Stack_One and push it into Stack_Two.
    2. Push the left and right child nodes of popped node into Stack_One.
  3. End Loop
  4. Pop out all the nodes from Stack_Two and print it.

See the animated image below and code for more understanding.

 

Postorder traversal
Postorder traversal

Complete Code:

import java.util.Stack;
public class PostorderTree {
public void postOrderRecursive(Node root) {
if (root != null) {
postOrderRecursive(root.left);
postOrderRecursive(root.right);
System.out.print(root.data + " ");
}
}
public void preorderIteration(Node root) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
// push the root node into first stack.
s1.push(root);
while (s1.isEmpty() == false) {
// take out the root and insert into second stack.
Node temp = s1.pop();
s2.push(temp);
// now we have the root, push the left and right child of root into
// the first stack.
if(temp.left!=null){
s1.push(temp.left);
}
if(temp.right!=null){
s1.push(temp.right);
}
}
//once the all node are traversed, take out the nodes from second stack and print it.
System.out.println("Preorder Traversal: ");
while(s2.isEmpty()==false){
System.out.print(s2.pop());
}
}
public static void main(String[] args) {
Node 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);
PostorderTree i = new PostorderTree();
i.postOrderRecursive(root);
System.out.println();
i.postOrderRecursive(root);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}

view raw
PostorderTree.java
hosted with ❤ by GitHub


Output:

4 5 2 6 7 3 1
4 5 2 6 7 3 1

2 thoughts on “Binary Tree-Postorder Traversal – Non Recursive Approach”

  1. On line 20 instead of “while(s1.isEmpty() == false)” you can use “while(!s1.isEmpty())”
    Same on line 35.

    line 36: should be System.out.print(s2.pop() + ” “);

    line 52: The call should be i.preorderIteration(root);

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.