Binary Tree Inorder Traversal Interview Question for Google

## Inorder Traversal of a Binary Tree

### Problem Description

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

### Examples

**Example 1:**

Input: `root = [1,null,2,3]`
Output: `[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]`

### Naive Recursive Solution

The most straightforward way to implement inorder traversal is using recursion. In inorder traversal, 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 inorderTraversalRecursive(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

Optimal Iterative Solution

To solve this problem iteratively, we can use a stack. The idea is to simulate the recursive calls using a stack.

def inorderTraversalIterative(root):
    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 (Iterative Solution)

The time complexity of the iterative solution is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once.

Explanation:

Each node is pushed onto the stack once.
Each node is popped from the stack once.
Therefore, the while loop iterates at most 2N times, where N is the number of nodes.

Big(O) Space Usage Analysis (Iterative Solution)

The space complexity of the iterative solution is O(H), where H is the height of the binary tree. In the worst case (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the average case (balanced tree), H is log(N), resulting in O(log(N)) space complexity.

Explanation:

The stack stores nodes that have not yet been visited.
In the worst case (skewed tree), all nodes can be in the stack at the same time.
In the average case (balanced tree), the maximum number of nodes in the stack is proportional to the height of the tree, which is log(N).

Edge Cases and Handling

Empty Tree:
- If the root is None, both the recursive and iterative solutions will correctly return an empty list [].
Single Node Tree:
- If the tree contains only one node, both solutions will return a list containing the value of that node.
Skewed Tree (Left or Right):
- Both solutions will handle skewed trees correctly, but the space complexity of the iterative solution will be O(N) in such cases.

Complete Code

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


def inorderTraversalRecursive(root):
    result = []

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)

    inorder(root)
    return result


def inorderTraversalIterative(root):
    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

# Example Usage:
# Construct a sample tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

# Perform inorder traversal using both methods
recursive_result = inorderTraversalRecursive(root)
iterative_result = inorderTraversalIterative(root)

print("Recursive Inorder Traversal:", recursive_result)  # Output: [1, 3, 2]
print("Iterative Inorder Traversal:", iterative_result)  # Output: [1, 3, 2]