// reversed-postorder rev_postorder(TreeNode root) { if (root == null) return; while (stack.size() > 0) { print(root.val); root = stack.pop(); postorder(root.right); -----> if (root.left != null) stack.push(root.left); postorder(root.left); if (root.right != null) stack.push(root.right); } }

// finally reverse the output postorder(root) = reverse(rev_postorder(root));

In the reversed-postorder traversal, we can see that this form of code is exactly like the preorder traversal. So, we can use the iteration code in preorder traversal.

Iteration Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public List<Integer> postorder(TreeNode root){ List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) { return result; } stack.push(root); while (stack.size() > 0) { TreeNode curr = stack.pop(); result.addFirst(curr.val); // addFirst() leads to a reversed result

if (curr.left != null) stack.push(curr.left); // left goes first if (curr.right != null) stack.push(curr.right); } return result; }

Time: $O(N)$ Space: $O(h)$

Iteration (inorder-like)

Like the inorder traversal, we go down to the left of the tree. But this time, we push a node p‘s right child to the stack if it is not null before pushing its left child. This actually means that in the future before visiting the node p, we would visit its right child first.

public List<Integer> postorderTraversal(TreeNode root){ if (root == null) { returnnew ArrayList<>(); } List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>();

TreeNode p = root; // no need to push into stack while (p != null || stack.size() > 0) { // go leftmost (this time we also push right child if it is not null) while (p != null) { if (p.right != null) stack.push(p.right); // push right child before p stack.push(p); p = p.left; } // p -> null

p = stack.pop(); // pop

// if p.right is at the top of stack, i.e. it is not yet processed if (stack.size() > 0 && p.right == stack.peek()) { stack.pop(); // pop its right from stack stack.push(p); // push p to stack to process it in the future p = p.right; // next time process p.right } else { // p.right == null OR p.right is processed result.add(p.val); p = null; // next time, don't visit left child } } return result; }

public List<Integer> postorderTraversal(TreeNode root){ if (root == null) { returnnew ArrayList<>(); } List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>();

TreeNode p = root; while (p != null || stack.size() > 0) { if (p != null) { if (p.right != null) stack.push(p.right); stack.push(p); p = p.left; } else { // p == null p = stack.pop(); if (stack.size() > 0 && p.right == stack.peek()) { // visit right child stack.pop(); stack.push(p); // push for future p = p.right; } else { // visit p result.add(p.val); p = null; // next time, don't visit left child } } } return result; }