## Tuesday, February 23, 2016

### Iterative Postorder Traversal | Set 1 (Using Two Stacks) - GeeksforGeeks

Iterative Postorder Traversal | Set 1 (Using Two Stacks) - GeeksforGeeks
Also check LeetCode - Binary Tree Postorder Traversal
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”.
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
def postOrderIterative(root):

# Create two stacks
s1 = []
s2 = []

# Push root to first stack
s1.append(root)

# Run while first stack is not empty
while(len(s1) >0):

# Pop an item from s1 and append it to s2
node = s1.pop()
s2.append(node)

# Push left and right children of removed item to s1
if node.left is not None:
s1.append(node.left)
if node.right is not None :
s1.append(node.right)
# Print all eleements of second stack
while(len(s2) > 0):
node = s2.pop()
print node.data,
http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
static Node root;
ArrayList<Integer> list = new ArrayList<Integer>();
// An iterative function to do postorder traversal of a given binary tree
ArrayList<Integer> postOrderIterative(Node node) {
Stack<Node> S = new Stack<Node>();

// Check for empty tree
if (node == null) {
return list;
}
S.push(node);
Node prev = null;
while (!S.isEmpty()) {
Node current = S.peek();
/* go down the tree in search of a leaf an if so process it and pop
stack otherwise move down */
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 {
S.pop();
}
/* go up the tree from left node, if the child is right
push it onto stack otherwise process parent and pop stack */
} else if (current.left == prev) {
if (current.right != null) {
S.push(current.right);
} else {
S.pop();
}

/* go up the tree from right node and after coming back
from right node process parent and pop stack */
} else if (current.right == prev) {
S.pop();
}
prev = current;
}
return list;
}
http://www.geeksforgeeks.org/iterative-preorder-traversal/
Given a Binary Tree, write an iterative function to print Preorder traversal of the given binary tree.
Refer this for recursive preorder traversal of Binary Tree. To convert an inherently recursive procedures to iterative, we need an explicit stack. Following is a simple stack based iterative process to print Preorder traversal.
1) Create an empty stack nodeStack and push root node to stack.
2) Do following while nodeStack is not empty.
….a) Pop an item from stack and print it.
….b) Push right child of popped item to stack
….c) Push left child of popped item to stack
Node root;

void iterativePreorder()
{
iterativePreorder(root);
}

// An iterative process to print preorder traversal of Binary tree
void iterativePreorder(Node node) {

// Base Case
if (node == null) {
return;
}

// Create an empty stack and push root to it
Stack<Node> nodeStack = new Stack<Node>();
nodeStack.push(root);

/* Pop all items one by one. Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first so that left is processed first */
while (nodeStack.empty() == false) {

// Pop the top item from stack and print it
Node mynode = nodeStack.peek();
System.out.print(mynode.data + " ");
nodeStack.pop();

// Push right and left children of the popped node to stack
if (mynode.right != null) {
nodeStack.push(mynode.right);
}
if (mynode.left != null) {
nodeStack.push(mynode.left);
}
}
}