In last two posts, iterative inorder and iterative preorder traversal, we learned how stack can be used to replace recursion and why recursive implementation can be dangerous in production environment. In this post, let’s discuss iterative postorder traversal of binary tree which is most complex of all traversals. What is post order traversal ? A traversal where left and right subtrees are visited before root is processed. For example, post order traversal of below tree would be : [1,6,5,12,16,14,10]
Iterative postorder traversal : Thoughts
Let’s look at the recursive implementation of postorder.
private void postOrder(Node root){ if(root == null) return; postOrder(root.left); postOrder(root.right); System.out.println(root.value); }
As we are going into left subtree and then directly to right subtree, without visiting root node. Can you find the similarity of structure between preorder and postorder implementation? Can we reverse the entire preorder traversal to get post order traversal? Reverse preorder will give us right child, left child and then root node, however order expected is left child, right child and root child.
Do you remember we pushed left and right node onto stack in order where right child went before left. How about reversing that?
There is one more problem with just reversing the preorder. In preorder, a node was processed as soon as popped from stack, like root node will be the first node to be processed. However, in postorder, root node is processed last. So, we actually need the order of processing too be reversed. What better than using a stack to store the reverse order of root nodes to processed.
All in all, we will be using two stacks, one to store left and right child, second to store processing order of nodes.
- Create two stacks s an out and push root node onto s
- While stack s is not empty
- op from stack s,
current
= s.pop - Put
current
onto stack out. - Put left and right child of
current
on to stack s
- op from stack s,
- Pop everything from out stack and process it.
Postorder traversal with two stacks : Implementation
package com.company.BST; import java.util.Stack; /** * Created by sangar on 22.5.18. */ public class BinarySearchTreeTraversal { private Node root; public void BinarySearchTree(){ root = null; } public class Node { private int value; private Node left; private Node right; public Node(int value) { this.value = value; this.left = null; this.right = null; } } public void insert(int value){ this.root = insertNode(this.root, value); } private Node insertNode(Node root, int value){ if(root == null){ //if this node is root of tree root = new Node(value); } else{ if(root.value > value){ //If root is greater than value, node should be added to left subtree root.left = insertNode(root.left, value); } else{ //If root is less than value, node should be added to right subtree root.right = insertNode(root.right, value); } } return root; } private void postOrder(Node root){ if(root == null) return; postOrder(root.left); postOrder(root.right); System.out.println(root.value); } public void postOrderTraversal(){ postOrderIterative(root); } private void postOrderIterative(Node root){ Stack<Node> out = new Stack<>(); Stack<Node> s = new Stack<>(); s.push(root); while(!s.empty()){ Node current = s.pop(); out.push(current); if(current.left != null) s.push(current.left); if(current.right != null) s.push(current.right); } while(!out.empty()){ System.out.println(out.pop().value); } } }
Complexity of iterative implementation is O(n) with additional space complexity of O(n).
Can we avoid using two stack, and do it with one stack? Problem with root in postorder traversal is that it is visited three times, moving down from parent, coming up from left child and coming up from right child. When should be the node processed? Well, when we are coming up from right child.
How can we keep track of how the current node was reached? If we keep previous pointer, there are three cases:
- Previous node is parent of current node, we reached node from parent node, nothing is done.
- Previous node is left child of current node, it means we have visited left child, but still not visited right child, move to right child of current node.
- Previous node is right child of current node, it means we have visited left and right child of current node, process the current node.
Let’s formulate postorder traversal algorithm then.
- Push root node onto stack s, set prev = null.
- Repeat below steps till stack is not empty (!s.empty())
current
= s.pop(), pop from the stack.- If (
prev
== null ||prev.left
== current ||prev.right
== current) then- If current.left != null, push
current.left
onto stack. - If current.right != null, push
current.right
onto stack. - If current.left == current.right == null, process
current
.
- If current.left != null, push
- If current.left == prev, i.e. moving up left child then
- If current.right == null, process
current
. - If current.right != null, push it to stack.
- If current.right == null, process
- If current.right == prev i.e moving up from right child
- process
current
. - prev = current, current = s.pop.
- process
Iterative Postorder traversal : Implementation
package com.company.BST; import java.util.Stack; /** * Created by sangar on 22.5.18. */ public class BinarySearchTreeTraversal { private Node root; public void BinarySearchTree(){ root = null; } public class Node { private int value; private Node left; private Node right; public Node(int value) { this.value = value; this.left = null; this.right = null; } } public void insert(int value){ this.root = insertNode(this.root, value); } private Node insertNode(Node root, int value){ if(root == null){ //if this node is root of tree root = new Node(value); } else{ if(root.value > value){ //If root is greater than value, node should be added to left subtree root.left = insertNode(root.left, value); } else{ //If root is less than value, node should be added to right subtree root.right = insertNode(root.right, value); } } return root; } private void inorder(Node root){ if(root == null) return; if(root.left != null) inorder(root.left); System.out.println(root.value); if(root.right != null) inorder(root.right); } private void preOrder(Node root){ if(root == null) return; System.out.println(root.value); preOrder(root.left); preOrder(root.right); } private void postOrder(Node root){ if(root == null) return; postOrder(root.left); postOrder(root.right); System.out.println(root.value); } public void postOrderTraversal(){ // postOrder(root); postOrderIterative2(root); //postOrderIterative(root); } private void postOrderIterative2(Node root){ Node prev = null; Stack<Node> s = new Stack<>(); s.push(root); while(!s.empty()){ Node current = s.peek(); if(prev == null || ( prev.left == current || prev.right == current )){ if(current.left != null) s.push(current.left); else if(current.right != null) s.push(current.right); } else if(prev == current.left){ if(current.right != null) s.push(current.right); }else{ System.out.println(current.value); s.pop(); } prev = current; } } }
Complexity of code is O(n) again, with additional space complexity of O(n).
Please share if there is something wrong or missing. If you want to contribute and share your learning with thousands of learners across the world, please reach out to us at [email protected]