What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?
30 Answers
import java.util.Stack;
public class IterativePostOrderTraversal extends BinaryTree {
public static void iterativePostOrderTraversal(Node root){
Node cur = root;
Node pre = root;
Stack<Node> s = new Stack<Node>();
if(root!=null)
s.push(root);
System.out.println("sysout"+s.isEmpty());
while(!s.isEmpty()){
cur = s.peek();
if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
if(cur.left!=null){
s.push(cur.left);
}
else if(cur.right!=null){
s.push(cur.right);
}
if(cur.left==null && cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.left){// we are traversing up the tree from the left
if(cur.right!=null){
s.push(cur.right);
}else if(cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.right){// we are traversing up the tree from the right
System.out.println(s.pop().data);
}
pre=cur;
}
}
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
Node root = bt.generateTree();
iterativePostOrderTraversal(root);
}
}
The logic of Post order traversal without using Recursion
In Postorder traversal, the processing order is left-right-current. So we need to visit the left section first before visiting other parts. We will try to traverse down to the tree as left as possible for each node of the tree. For each current node, if the right child is present then push it into the stack before pushing the current node while root is not NULL/None. Now pop a node from the stack and check whether the right child of that node exists or not. If it exists, then check whether it's same as the top element or not. If they are same then it indicates that we are not done with right part yet, so before processing the current node we have to process the right part and for that pop the top element(right child) and push the current node back into the stack. At each time our head is the popped element. If the current element is not the same as the top and head is not NULL then we are done with both the left and right section so now we can process the current node. We have to repeat the previous steps until the stack is empty.
def Postorder_iterative(head):
if head is None:
return None
sta=stack()
while True:
while head is not None:
if head.r:
sta.push(head.r)
sta.push(head)
head=head.l
if sta.top is -1:
break
head = sta.pop()
if head.r is not None and sta.top is not -1 and head.r is sta.A[sta.top]:
x=sta.pop()
sta.push(head)
head=x
else:
print(head.val,end = ' ')
head=None
print()
Here is a Python version too ::
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def postOrderIterative(root):
if root is None :
return
s1 = []
s2 = []
s1.append(root)
while(len(s1)>0):
node = s1.pop()
s2.append(node)
if(node.left!=None):
s1.append(node.left)
if(node.right!=None):
s1.append(node.right)
while(len(s2)>0):
node = s2.pop()
print(node.data)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)
Here is the output ::
So you can use one stack to do a post order traversal.
private void PostOrderTraversal(Node pos) {
Stack<Node> stack = new Stack<Node>();
do {
if (pos==null && (pos=stack.peek().right)==null) {
for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
} else if(pos!=null) {
stack.push(pos);
pos=pos.left;
}
} while (!stack.isEmpty());
}
Two methods to perform Post Order Traversal without Recursion:
1. Using One HashSet of Visited Nodes and One stack for backtracking:
private void postOrderWithoutRecursion(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visited = new HashSet<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
visited.add(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null || visited.contains(root.right)) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
root = root.right;
}
}
}
}
Time Complexity: O(n)
Space Complexity: O(2n)
2. Using Tree Altering method:
private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
TreeNode temp = root.right;
root.right = null;
root = temp;
}
}
}
}
Time Complexity: O(n)
Space Complexity: O(n)
TreeNode Class:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
Here's a short (the walker is 3 lines) version that I needed to write in Python for a general tree. Of course, works for a more limited binary tree too. Tree is a tuple of the node and list of children. It only has one stack. Sample usage shown.
def postorder(tree):
def do_something(x): # Your function here
print(x),
def walk_helper(root_node, calls_to_perform):
calls_to_perform.append(partial(do_something, root_node[0]))
for child in root_node[1]:
calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
calls_to_perform = []
calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
while calls_to_perform:
calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))
d c b a
The simplest solution, it may look like not the best answer but it is easy to understand. And I believe if you have understood the solution then you can modify it to make the best possible solution
// using two stacks
public List<Integer> postorderTraversal(TreeNode root){
Stack<TreeNode> st=new Stack<>();
Stack<TreeNode> st2=new Stack<>();
ArrayList<Integer> al = new ArrayList<Integer>();
if(root==null)
return al;
st.push(root); //push the root to 1st stack
while(!st.isEmpty())
{
TreeNode curr=st.pop();
st2.push(curr);
if(curr.left!=null)
st.push(curr.left);
if(curr.right!=null)
st.push(curr.right);
}
while(!st2.isEmpty())
al.add(st2.pop().val);
//this ArrayList contains the postorder traversal
return al;
}
Simple Intuitive solution in python.
while stack:
node = stack.pop()
if node:
if isinstance(node,TreeNode):
stack.append(node.val)
stack.append(node.right)
stack.append(node.left)
else:
post.append(node)
return post
This is what I've come up for post order iterator:
class PostOrderIterator
implements Iterator<T> {
private Stack<Node<T>> stack;
private Node<T> prev;
PostOrderIterator(Node<T> root) {
this.stack = new Stack<>();
recurse(root);
this.prev = this.stack.peek();
}
private void recurse(Node<T> node) {
if(node == null) {
return;
}
while(node != null) {
stack.push(node);
node = node.left;
}
recurse(stack.peek().right);
}
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public T next() {
if(stack.peek().right != this.prev) {
recurse(stack.peek().right);
}
Node<T> next = stack.pop();
this.prev = next;
return next.value;
}
}
Basically, the main idea is that you should think how the initialization process puts the first item to print on the top of the stack, while the rest of the stack follow the nodes that would have been touched by the recursion. The rest would just then become a lot easier to nail.
Also, from design perspective, PostOrderIterator is an internal class exposed via some factory method of the tree class as an Iterator<T>.
In post-order traversal, he left child of a node is visited first, followed by its right child, and finally the node itself. This tree traversal method is similar to depth first search (DFS) traversal of a graph.
Time Complexity: O(n)
Space Complexity: O(n)
Below is the iterative implementation of post-order traversal in python:
class Node:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
def post_order(node):
if node is None:
return []
stack = []
nodes = []
last_node_visited = None
while stack or node:
if node:
stack.append(node)
node = node.left
else:
peek_node = stack[-1]
if peek_node.right and last_node_visited != peek_node.right:
node = peek_node.right
else:
nodes.append(peek_node.data)
last_node_visited = stack.pop()
return nodes
def main():
'''
Construct the below binary tree:
15
/ \
/ \
/ \
10 20
/ \ / \
8 12 16 25
'''
root = Node(15)
root.left = Node(10)
root.right = Node(20)
root.left.left = Node(8)
root.left.right = Node(12)
root.right.left = Node(16)
root.right.right = Node(25)
print(post_order(root))
if __name__ == '__main__':
main()
For writing iterative equivalents of these recursive methods, we can first understand how the recursive methods themselves execute over the program's stack. Assuming that the nodes do not have their parent pointer, we need to manage our own "stack" for the iterative variants.
One way to start is to see the recursive method and mark the locations where a call would "resume" (fresh initial call, or after a recursive call returns). Below these are marked as "RP 0", "RP 1" etc ("Resume Point"). For the case of postorder traversal:
void post(node *x)
{
/* RP 0 */
if(x->lc) post(x->lc);
/* RP 1 */
if(x->rc) post(x->rc);
/* RP 2 */
process(x);
}
Its iterative variant:
void post_i(node *root)
{
node *stack[1000];
int top;
node *popped;
stack[0] = root;
top = 0;
popped = NULL;
#define POPPED_A_CHILD() \
(popped && (popped == curr->lc || popped == curr->rc))
while(top >= 0)
{
node *curr = stack[top];
if(!POPPED_A_CHILD())
{
/* type (x: 0) */
if(curr->rc || curr->lc)
{
if(curr->rc) stack[++top] = curr->rc;
if(curr->lc) stack[++top] = curr->lc;
popped = NULL;
continue;
}
}
/* type (x: 2) */
process(curr);
top--;
popped = curr;
}
}
The code comments with (x: 0) and (x: 2) correspond to the "RP 0" and "RP 2" resume points in the recursive method.
By pushing both the lc and rc pointers together, we have removed the need of keeping the post(x) invocation at resume-point 1 while the post(x->lc) completes its execution. That is, we could directly shift the node to "RP 2", bypassing "RP 1". So, there is no node kept on stack at "RP 1" stage.
The POPPED_A_CHILD macro helps us deduce one of the two resume-points ("RP 0", or "RP 2").
Related