Inorder Traversal of a Binary Tree

Problem Description

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

Naive Approach: Recursive Solution

The most straightforward way to perform an inorder traversal is using recursion. In inorder traversal, we visit the left subtree, then the root, and finally the right subtree.

Code:

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

def inorder_recursive(root):
    if root is None:
        return []
    
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the call stack during recursion. In the worst case (skewed tree), H can be N, leading to O(N) space complexity. In the best case (balanced tree), H is log(N), leading to O(log(N)) space complexity.

Optimal Approach: Iterative Solution

An iterative approach uses a stack to simulate the recursive calls. This can be useful for very large trees where recursion might lead to stack overflow errors.

Algorithm:

1. Initialize an empty stack.
2. Set the current node to the root.
3. While the current node is not None or the stack is not empty:
   • If the current node is not None:
     • Push the current node onto the stack.
     • Move to the left child of the current node.
   • Else:
     • Pop a node from the stack.
     • Add its value to the result list.
     • Move to the right child of the popped node.
4. Return the result list.

Code:

def inorder_iterative(root):
    result = []
    stack = []
    current = root
    
    while current or stack:
        if current:
            stack.append(current)
            current = current.left
        else:
            current = stack.pop()
            result.append(current.val)
            current = current.right
            
    return result

Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. In the worst case (skewed tree), H can be N, leading to O(N) space complexity because the stack might contain all nodes. In the best case (balanced tree), H is log(N), leading to O(log(N)) space complexity.

Edge Cases

• Empty Tree: If the root is None, the traversal should return an empty list.
• Single Node Tree: If the tree has only one node, the traversal should return a list containing only that node's value.

Summary

Both the recursive and iterative solutions have the same time complexity O(N). The recursive approach has a space complexity of O(H) due to the call stack, while the iterative approach also has a space complexity of O(H) due to the stack. The iterative approach is often preferred for very large trees to avoid potential stack overflow errors associated with deep recursion.