# LeetCode 94: Binary Tree Inorder Traversal

## Problem Restatement

We are given the root of a binary tree.

We need to return the inorder traversal of the tree's node values.

Inorder traversal means:

```python
left subtree
current node
right subtree
```

The official constraints say the number of nodes is between `0` and `100`, and each node value is between `-100` and `100`. The follow-up asks for an iterative solution.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | List of node values in inorder order |
| Empty tree | Return `[]` |
| Visit order | Left subtree, node, right subtree |

Function shape:

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

## Examples

Example 1:

```python
root = [1, None, 2, 3]
```

Tree shape:

```python
    1
     \
      2
     /
    3
```

Inorder traversal:

```python
left of 1 -> none
visit 1
right of 1 -> node 2
left of 2 -> node 3
visit 3
visit 2
```

Answer:

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

Example 2:

```python
root = []
```

There are no nodes.

Answer:

```python
[]
```

Example 3:

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

Only one node exists.

Answer:

```python
[1]
```

## First Thought: Recursive DFS

Inorder traversal is naturally recursive.

For each node:

1. Traverse the left child.
2. Add the current node value.
3. Traverse the right child.

This directly follows the definition.

## Algorithm

Create an empty result list:

```python
ans = []
```

Define a helper:

```python
dfs(node)
```

Inside the helper:

1. If `node` is `None`, return.
2. Traverse `node.left`.
3. Append `node.val`.
4. Traverse `node.right`.

Return `ans`.

## Correctness

For any node, inorder traversal requires that every node in its left subtree appears before the node itself, and every node in its right subtree appears after the node itself.

The recursive helper does exactly this.

It first applies the same rule to the left subtree, then records the current node, then applies the same rule to the right subtree.

The base case handles an empty subtree by adding nothing.

Therefore, every node is visited once in inorder order.

## Complexity

Let:

```python
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 equals tree height |
| Output space | `O(n)` | The result list stores all node values |

In the worst case, `h = n` for a skewed tree.

In a balanced tree, `h = log n`.

## Recursive Implementation

```python
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ans = []

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

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

        dfs(root)
        return ans
```

## Iterative Stack Implementation

The follow-up asks for an iterative solution.

The recursive call stack can be replaced with an explicit stack.

The idea is:

1. Keep going left and push nodes into the stack.
2. When there is no more left child, pop one node.
3. Visit that node.
4. Move to its right child.

## Iterative Algorithm

Start with:

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

While `cur` exists or `stack` is not empty:

1. While `cur` exists, push it and move left.
2. Pop the top node.
3. Append its value.
4. Move to its right child.

## Iterative Implementation

```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ans = []
        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            ans.append(cur.val)
            cur = cur.right

        return ans
```

## Code Explanation

The inner loop:

```python
while cur:
    stack.append(cur)
    cur = cur.left
```

pushes the current node and all left ancestors.

When it stops, there is no more left subtree to process.

Then:

```python
cur = stack.pop()
ans.append(cur.val)
```

visits the nearest unvisited node.

Finally:

```python
cur = cur.right
```

moves into the right subtree.

This exactly simulates recursive inorder traversal.

## 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)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    assert s.inorderTraversal(root) == [1, 3, 2]

    assert s.inorderTraversal(None) == []

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

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, None, 2, 3]` | Main example |
| Empty tree | No nodes |
| Single node | Smallest non-empty tree |
| Balanced tree | Checks left-root-right order |
| Left-skewed tree | Checks deep left traversal |