Binary Tree Inorder Traversal

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

For example, if the input is root = [1,null,2,3], the output should be [1,3,2] because you visit the left subtree (None), then the root (1), then the right subtree (2 which has left child 3, so you visit 3 then 2). Another example, if the input is root = [1,2,3,4,5,null,8,null,null,6,7,9], then the output should be [4,2,6,5,7,1,3,9,8] because that's the inorder traversal of the tree.

Recursive solution is trivial, could you do it iteratively?

## Question: Binary Tree Inorder Traversal

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]`

Solution

1. Recursive Solution

The most intuitive way to perform an inorder traversal is using recursion. The inorder traversal visits the left subtree, then the current node, then the right subtree.

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

2. Iterative Solution

An iterative solution uses a stack to keep track of the nodes. The algorithm proceeds as follows:

1. Initialize an empty stack.
2. Push the root node onto the stack.
3. While the stack is not empty:
   • Go to the leftmost node by pushing all left children onto the stack.
   • Pop the top node from the stack.
   • Add the node's value to the result.
   • If the node has a right child, push the right child onto the stack.

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) Analysis

• Time Complexity: O(n), where n is the number of nodes in the binary tree. Both the recursive and iterative solutions visit each node exactly once.
• Space Complexity:
  • Recursive: O(h) in the average case and O(n) in the worst case (skewed tree), where h is the height of the tree. This is due to the call stack.
  • Iterative: O(h) in the average case and O(n) in the worst case (skewed tree), where h is the height of the tree. This is due to the stack.

Edge Cases

1. Empty Tree:
   • If the root is None, the algorithm should return an empty list [].
2. Single Node Tree:
   • If the root is the only node, the algorithm should return a list containing the root's value, e.g., [1].
3. Skewed Tree (Left or Right):
   • The algorithm should handle skewed trees correctly, ensuring all nodes are visited in the correct order.
4. Deeply Nested Tree:
   • The algorithm should work efficiently even for deeply nested trees, without causing stack overflow errors (the iterative method is often preferred in such cases).