# LeetCode 145: Binary Tree Postorder Traversal

## Problem Restatement

We are given the root of a binary tree.

Return the postorder traversal of its node values.

Postorder traversal visits nodes in this order:

```text
left subtree -> right subtree -> root
```

If the tree is empty, return an empty list.

LeetCode also includes a follow-up asking for an iterative solution. ([leetcode.com](https://leetcode.com/problems/binary-tree-postorder-traversal/?utm_source=chatgpt.com))

## Examples

Example 1:

```text
    1
     \
      2
     /
    3
```

Traversal order:

```text
visit left of 1: none
visit right subtree rooted at 2
visit left of 2: 3
visit right of 2: none
visit 2
visit 1
```

Output:

```python
[3, 2, 1]
```

Example 2:

```python
root = []
```

Output:

```python
[]
```

Example 3:

```python
root = [1]
```

Output:

```python
[1]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root: Optional[TreeNode]` |
| Output | `list[int]` |
| Traversal order | Left subtree, right subtree, root |
| Empty tree | Return `[]` |

Function shape:

```python
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ...
```

## Core Idea

Postorder traversal processes children before the current node.

At every node:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the current node.

So the recursive structure directly follows the traversal definition:

```python
postorder(node.left)
postorder(node.right)
visit(node)
```

## Recursive Algorithm

Create an empty result list.

Define:

```python
dfs(node)
```

For each node:

1. If the node is `None`, return.
2. Traverse the left subtree.
3. Traverse the right subtree.
4. Append the current node value.

Return the result list.

## Correctness

For any subtree rooted at `node`, postorder traversal requires processing:

1. all nodes in the left subtree
2. all nodes in the right subtree
3. the root node last

The algorithm recursively traverses the left subtree first, producing the left subtree in postorder.

Then it recursively traverses the right subtree, producing the right subtree in postorder.

Finally, it appends the current node value.

Therefore, every subtree is processed in left-right-root order, which is exactly postorder traversal.

If the tree is empty, the helper immediately returns and the result list remains empty.

Thus, the algorithm correctly returns the postorder traversal of the tree.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Number of nodes |
| `h` | Height of the tree |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | Recursion stack depth |

In the worst case, a skewed tree has height `n`.

## Recursive Implementation

```python
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []

        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return

            dfs(node.left)
            dfs(node.right)
            result.append(node.val)

        dfs(root)
        return result
```

## Code Explanation

The traversal result is stored in:

```python
result = []
```

The helper processes one subtree:

```python
def dfs(node: Optional[TreeNode]) -> None:
```

The base case:

```python
if node is None:
    return
```

stops recursion at missing children.

Postorder visits the left subtree first:

```python
dfs(node.left)
```

Then the right subtree:

```python
dfs(node.right)
```

Finally, visit the root:

```python
result.append(node.val)
```

After the traversal finishes:

```python
return result
```

returns the full postorder sequence.

## Iterative Solution

Postorder is trickier iteratively because the root must be processed last.

One elegant trick:

1. Perform modified preorder traversal:
   - root
   - right
   - left
2. Reverse the result.

Why?

Normal preorder:

```text
root -> left -> right
```

Modified preorder:

```text
root -> right -> left
```

Reverse it:

```text
left -> right -> root
```

which is postorder.

## Iterative Implementation

```python
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            if node.left is not None:
                stack.append(node.left)

            if node.right is not None:
                stack.append(node.right)

        return result[::-1]
```

## Iterative Code Explanation

Start with the root:

```python
stack = [root]
```

Each iteration:

```python
node = stack.pop()
```

visits the current node:

```python
result.append(node.val)
```

Push the left child first:

```python
if node.left is not None:
    stack.append(node.left)
```

Then the right child:

```python
if node.right is not None:
    stack.append(node.right)
```

Because the stack is LIFO, the right child is processed before the left child.

So traversal order becomes:

```text
root -> right -> left
```

Finally:

```python
return result[::-1]
```

reverses it into:

```text
left -> right -> root
```

which is postorder traversal.

## Alternative Iterative Method with Visited State

Another iterative approach uses explicit traversal state.

Each stack item stores:

```python
(node, visited)
```

If `visited` is false:

1. push the node back as visited
2. push right child
3. push left child

If `visited` is true:

1. append node value

```python
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        result = []
        stack = [(root, False)]

        while stack:
            node, visited = stack.pop()

            if visited:
                result.append(node.val)
                continue

            stack.append((node, True))

            if node.right:
                stack.append((node.right, False))

            if node.left:
                stack.append((node.left, False))

        return result
```

This follows the recursive structure more directly.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    assert s.postorderTraversal(root) == [3, 2, 1]

    assert s.postorderTraversal(None) == []

    root = TreeNode(1)
    assert s.postorderTraversal(root) == [1]

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )
    assert s.postorderTraversal(root) == [4, 5, 2, 3, 1]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.postorderTraversal(root) == [3, 2, 1]

    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert s.postorderTraversal(root) == [3, 2, 1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard LeetCode example | Mixed left/right structure |
| Empty tree | Returns empty list |
| Single node | Smallest non-empty tree |
| Full tree | Confirms left-right-root ordering |
| Left-skewed tree | Deep recursive left traversal |
| Right-skewed tree | Deep recursive right traversal |