# Post-order Traversalby Isai Damier, Android Engineer @ Google

```/**************************************************************************
* Author: Isai Damier
* Title: Post-order Traversal
* Project: geekviewpoint
* Package: algorithms
*
* Time Complexity of Solution:
*   Best = Average = Worst = O(n).
*
* Description: visit left child; visit right child; visit node.
*
* Technical Details: The iterative implementation of postorder is not as
*   simple as preorder or postorder. Here, the visited nodes must be
*   marked as such; so as not to loop endlessly.
*
*    0] preliminary checks: if root is null, return.
*    1] create a stack and push root into it.
*    2] create a map to track visited nodes
*    3] while stack is not empty
*       1) peek into stack as n
*       2) if n.left is not null and is not marked as visited
*          THEN add n.left to stack
*       3) ELSE if n.right is not null and is not marked as
*          visited THEN add n.right to stack
*       4)ELSE visit n, mark n  as visited, and pop n from stack
*
*  Alternate Algorithm: recursive:
*
*     public void postorder(){
*       postorder(root);
*     }
*
*     public void postorder(Node n){
*       if(null != n){
*         postorder(n.left);
*         postorder(n.right);
*         visit(n);
*       }
*     }
*
**************************************************************************/
public void postorder() {
if (null == root) {
return;
}

Stack<Node> stack = new Stack<Node>();
stack.push(root);
Map<Integer, Node> visited = new HashMap<Integer, Node>();
Node n;

while (!stack.isEmpty()) {
n = stack.peek();

if (null != n.left && !visited.containsValue(n.left)) {
stack.push(n.left);
} else if (null != n.right && !visited.containsValue(n.right)) {
stack.push(n.right);
} else {
visit(n);
visited.put(n.data, n);
}
}
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/**
* Test of postorder method, of class BST.
*/
@Test
public void testPostorder() {
System.out.println(""postorder"");
final ByteArrayOutputStream output = new ByteArrayOutputStream();
System.setOut(new PrintStream(output));

BST bst = new BST();
int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400};
Integer[] pos = {35, 25, 75, 50, 125, 175, 150, 100, 212, 225, 275, 250,
312, 325, 400, 375, 350, 300, 200};
String expected = """";
assertEquals(expected, output.toString());
for (int i : pos) {
expected += i + ""\n"";
}