Post-order Traversal
by 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);
      stack.pop();//pop last node added
    }
  }
}

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"";
    }

    //load data into tree
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test postorder
    bst.postorder();
    assertEquals(expected, output.toString());
    assertEquals(treeTape.length, bst.size());//has correct size
    System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));
    System.out.println(""done with postorder"");
  }
}