Problem: Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

For example:

Consider the binary tree represented by the array [1,null,2,3]. The tree looks like this:

  1
   \ 
    2
   / 
  3

The inorder traversal would be [1, 3, 2].

Another example, consider the tree [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]. This tree looks like this:

      1
     / \
    2   3
   / \   \
  4   5   8
     / \ /
    6   7 9

The inorder traversal would be [4, 2, 6, 5, 7, 1, 3, 9, 8].

Edge cases include:

• An empty tree represented by []. The expected output is [].
• A single-node tree represented by [1]. The expected output is [1].

Write a function that takes the root of a binary tree as input and returns a list containing the inorder traversal of the tree. Can you provide both a recursive and an iterative solution? Additionally, can you analyze the time and space complexity of each solution?

# Binary Tree Inorder Traversal

## Problem Description

Given the root of a binary tree, return the inorder traversal of its nodes' values.

### Example 1:

**Input:** `root = [1, null, 2, 3]`
**Output:** `[1, 3, 2]`

**Explanation:**

  1
   \
    2
   / 
  3

The inorder traversal is [1, 3, 2].

### Example 2:

**Input:** `root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]`
**Output:** `[4, 2, 6, 5, 7, 1, 3, 9, 8]`

**Explanation:**

      1
     / \
    2   3
   / \   \
  4   5   8
     / \ /
    6   7 9

The inorder traversal is [4, 2, 6, 5, 7, 1, 3, 9, 8].

## Solution

### Recursive Solution

The recursive approach is straightforward. We visit the left subtree, then the current node, and finally the right subtree.

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


def inorder_recursive(root: TreeNode) -> list[int]:
    result = []

    def traverse(node: TreeNode):
        if node:
            traverse(node.left)
            result.append(node.val)
            traverse(node.right)

    traverse(root)
    return result

Iterative Solution

The iterative approach uses a stack to simulate the recursive calls.

def inorder_iterative(root: TreeNode) -> list[int]:
    result = []
    stack = []
    curr = root

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

        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right

    return result

Big(O) Runtime Analysis

Both the recursive and iterative solutions have a time complexity of O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Big(O) Space Usage Analysis

• Recursive Solution: The space complexity is O(h), where h is the height of the binary tree, due to the call stack. In the worst case (skewed tree), h = n, so the space complexity is O(n). In the best case (balanced tree), h = log n, so the space complexity is O(log n).
• Iterative Solution: The space complexity is O(h), where h is the height of the binary tree, due to the stack. In the worst case (skewed tree), h = n, so the space complexity is O(n). In the best case (balanced tree), h = log n, so the space complexity is O(log n).

Edge Cases

1. Empty Tree: If the root is None, return an empty list.
2. Single Node Tree: If the tree contains only one node, return a list containing that node's value.
3. Skewed Tree (Left or Right): The algorithm should handle skewed trees efficiently, without causing a stack overflow (especially important for the recursive solution in languages with limited stack size).

Here's how the edge cases are handled:

• If the root is None, both solutions return an empty list [].
• If the root is a single node, both solutions correctly return a list containing that node's value.
• Skewed trees are handled correctly by both solutions; the iterative solution avoids stack overflow issues.