**Solution. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)**

**Explanation**

**Postorder:** left, right, root

**Preorder :** root, right, left

**Postorder** is kind of **reverse order** of **Preorder**. (Just travel to tree's right leaf at first, instead of left leaf).

- Start from root, recursively travel to each passed node's right child until reach the tree's right leaf
- Then pop to right leaf's higher level node A
- And switch to A's left branch

Keep the above steps until the current node is null and stack is empty.

**Trick:** Add node's value to array's first position to reverse the order.

```
/*
Solution1. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)
*/
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = Stack<TreeNode>()
var cur: TreeNode? = root // Set `root` as `cur`
while cur != nil || !stack.isEmpty {// <-- !stack.isEmpty
if cur != nil { // 1. Push cur's RIGHT branch to stack until leaf
res.insert(cur!.val, at: 0) // 2. Insert cur's val at 0
stack.push(cur!)
cur = cur!.right
} else {
cur = stack.pop() // 3. Backtrack to higher level node A (stack isn't empty, via while/if condition)
cur = cur!.left // 4. Switch to the higher node A's LEFT branch
}
}
return res
}
```

```
/*
Solution2. Translate from recusive solution. time = O(n) - each node is visited once; space = O(n)
CAN'T BE USED for in-order traversal, because root poping is after all left nodes poping (root poping is at beginning for Pre/Post traversal)
*/
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
guard let root = root else {return res}
var stack = Stack<TreeNode>()
stack.push(root) // Push: root
while !stack.isEmpty() {
let curr = stack.pop()! // Pop: the last pushed node
res.insert(curr.val, at: 0) // <--insert at 0
if curr.left != nil { // Push: curr.left
stack.push(curr.left!)
}
if curr.right != nil{ // <--Push: curr.right later than curr.left (Stack reverses order of execution)
stack.push(curr.right!)
}
}
return res
}
```