## 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();`

`                    ``list.add(current.data);`

`                ``}`

`                ``/* 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();`

`                    ``list.add(current.data);`

`                ``}`

`                `

`                ``/* 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();`

`                ``list.add(current.data);`

`            ``}`

`            ``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);`
`            ``}`
`        ``}`
`    ``}`