# 3 different ways to do post order traversal (ALL iterative and O(N))

• State & Call Stack mimic

``````    public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null) return ret;

Stack<State> stack = new Stack<>();
stack.push(new State(root, false, false));

while(!stack.isEmpty()) {
State state = stack.pop();
TreeNode node = state.node;
if(node == null) continue;
if(state.completedRight) {
} else if(state.completedLeft) {
stack.push(new State(node, true, true));
stack.push(new State(node.right, false, false));
} else {
stack.push(new State(node, true, false));
stack.push(new State(node.left, false, false));
}
}

return ret;
}

private static class State {
final TreeNode node;
final boolean completedLeft;
final boolean completedRight;

State(TreeNode node, boolean completedLeft, boolean completedRight) {
this.node = node;
this.completedLeft = completedLeft;
this.completedRight = completedRight;
}
}
``````

Double stack (second stack to record right direction travelling)

``````    public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();

Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> rights = new Stack<>();
pushAllLefts(root, stack);

while(!stack.isEmpty()) {
TreeNode next = stack.peek();
if(!rights.isEmpty() && rights.peek() == next) {
stack.pop();
rights.pop();
} else {
rights.push(next);
pushAllLefts(next.right, stack);
}
}

return ret;
}

private static void pushAllLefts(TreeNode node, Stack<TreeNode> stack) {
while(node != null) {
stack.push(node);
node = node.left;
}
}
``````

Morris: right -> left -> current. and reverse order

``````    public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null) return ret;

stack.push(root);
while(!stack.isEmpty()) {
TreeNode cur = stack.pop();