Binary Tree Inorder Traversal

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

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

Explanation:

    1
     \
      2
     /
    3

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]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

# Binary Tree Inorder Traversal

## Problem Description

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

## Example

For example, given the following binary tree:

1
 \
  2
 /
3

The inorder traversal should be `[1, 3, 2]`.

## Naive Solution (Recursive)

The most straightforward way to perform an inorder traversal is to use recursion. The algorithm is as follows:

1.  Traverse the left subtree.
2.  Visit the root.
3.  Traverse the right subtree.

```python
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: TreeNode) -> list[int]:
        result = []

        def inorder(node: TreeNode):
            if not node:
                return

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

        inorder(root)
        return result

Optimal Solution (Iterative)

An iterative solution can be achieved using a stack. The algorithm is as follows:

1. Initialize an empty stack.
2. Push the root node onto the stack.
3. While the stack is not empty:
   • If the current node has a left child, push the left child onto the stack and move to the left child.
   • Otherwise, pop the top node from the stack, add its value to the result, and move to the right child.

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: 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) Run-time Analysis

The time complexity for both the recursive and iterative solutions is O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once.

Big(O) Space Usage Analysis

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

Edge Cases

• Empty Tree: If the root is None, the function should return an empty list.
• Single Node Tree: If the tree contains only one node, the function should return a list containing the value of that node.
• Skewed Tree (Left or Right): The algorithm should handle skewed trees correctly, ensuring that all nodes are visited in the correct order.