# Iterative Post-Order Traversal

Hard

Implement an iterative, post-order traversal of a given binary tree, return the list of keys of each node in the tree as it is post-order traversed.

**Examples**

&#x20;       5

&#x20;     /    \\

&#x20;   3        8

&#x20; /   \        \\

1      4        11

Post-order traversal is \[1, 4, 3, 11, 8, 5]

**Corner Cases**

* What if the given binary tree is null? Return an empty list in this case.

**How is the binary tree represented?**

We use the level order traversal sequence with a special symbol "#" denoting the null node.

**For Example:**

The sequence \[1, 2, 3, #, #, 4] represents the following binary tree:

&#x20;   1

&#x20; /   \\

&#x20;2     3

&#x20;     /

&#x20;   4

Solution: self, left, right check, then flip

since the goal is to obtain nodes in order of

1. left child
2. right child
3. self

We use a stack to perform&#x20;

1. poll self
2. offer left child
3. offer right child

Since stacks are LIFO, this will result in&#x20;

1. add self&#x20;
2. add right
3. add left

Finally reverse the results

```java
public class Solution {
  public List<Integer> postOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null){
      return result;
    }
    Deque<TreeNode> preOrder = new LinkedList<>();
    preOrder.offerFirst(root);
    while(!preOrder.isEmpty()){
      TreeNode current = preOrder.pollFirst();
      result.add(current.key);
      if (current.left != null){
        preOrder.offerFirst(current.left);
      }
      if (current.right != null){
        preOrder.offerFirst(current.right);
      }
    }
    Collections.reverse(result);
    return result;
  }


}

```

TC: O(N)

SC: O(N)

