## Tree Node Definition#

``````# Definition for a binary tree node.
from typing import List

class TreeNode:
def __init__(self, x: int) -> None:
self.val = x
self.left = None
self.right = None
``````

## Recursive Implementation#

### `left` ➡️ `right` ➡️ `root`#

``````class Solution:
def traversal(self, root: 'TreeNode', out=None) -> List[List[int]]:
"""
0
/     \
1        2
/   \
3       4
/   \
6       9

Post-order...: [3, 6, 9, 4, 1, 2, 0]

T: O(N)
S: O(N) worst case; O(log N) average
"""

if out is None:
out = []

if not root:
return []

self.traversal(root.left, out=out)
self.traversal(root.right, out=out)
out.append(root.val)

return out
``````

## Iterative Implementation#

### `left` ➡️ `right` ➡️ `root`#

``````from collections import deque
class Solution:
def traversal(self, root: 'TreeNode', out=None)->List[List[int]]:
"""
0
/     \
1        2
/   \
3       4
/   \
6       9

Post-order...: [3, 6, 9, 4, 1, 2, 0]

T: O(N)
S: O(N)
"""

if out is None:
out = []

if not root:
return []

stack = deque()
curr = root

while curr or stack:
# Add each node on the left branch twice
while curr:
stack.append(curr)
stack.append(curr)
curr = curr.left

curr = stack.pop()

# If the top of the stack equals curr,
# move to the right branch
if stack and stack[-1] == curr:
curr = curr.right
else:
# Otherwise, add the current node value
out.append(curr.val)
curr = None

return out
``````