94. Binary Tree Inorder Traversal

This problem asks for an inorder traversal of a binary tree. Inorder traversal visits nodes in the order: left subtree, root, right subtree. We'll explore three solutions: recursive, iterative using a stack, and iterative using Morris traversal.

Solution 1: Recursive Approach

This is the most straightforward approach, leveraging the inherent recursive nature of trees.

Algorithm:

1. If the node is null, return.
2. Recursively traverse the left subtree.
3. Add the current node's value to the result list.
4. Recursively traverse the right subtree.

Code (Python):

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
 
        def dfs(node):
            if node:
                dfs(node.left)
                result.append(node.val)
                dfs(node.right)
 
        dfs(root)
        return result

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N. In the best case (a balanced tree), H is log₂N.

Solution 2: Iterative Approach with Stack

This approach avoids recursion by using a stack to simulate the recursive calls.

Algorithm:

1. Initialize an empty stack stack and an empty result list result.
2. While the stack is not empty or the current node is not null:
   • If the current node is not null: push the current node onto the stack and move to its left child.
   • Otherwise (current node is null): pop a node from the stack, add its value to result, and move to its right child.

Code (Python):

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        current = root
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        return result

Time Complexity: O(N) - Each node is visited and processed once.

Space Complexity: O(H) - In the worst case (a skewed tree), the stack can grow to the height of the tree (H). In a balanced tree, H = log₂N.

Solution 3: Morris Traversal (In-order)

This approach is space-efficient, achieving O(1) space complexity. It cleverly uses the tree structure itself to track the traversal.

Algorithm:

1. Initialize an empty result list result.
2. While the current node is not null:
   • If the current node's left child is null: add the current node's value to result and move to the right child.
   • Otherwise: find the inorder predecessor (rightmost node in the left subtree).
     • If the predecessor's right child is null: set the predecessor's right child to the current node and move to the left child.
     • Otherwise: add the current node's value to result, set the predecessor's right child to null (to disconnect the temporary link), and move to the right child.

Code (Python):

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        current = root
        while current:
            if not current.left:
                result.append(current.val)
                current = current.right
            else:
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right
                if not predecessor.right:
                    predecessor.right = current
                    current = current.left
                else:
                    result.append(current.val)
                    predecessor.right = None
                    current = current.right
        return result

Time Complexity: O(N) - Each node is visited and processed once.

Space Complexity: O(1) - No extra space is used beyond a few pointers.

Summary Table:

| Approach | Time Complexity | Space Complexity | |-----------------|-----------------|--------------------| | Recursive | O(N) | O(H) | | Iterative (Stack)| O(N) | O(H) | | Morris Traversal| O(N) | O(1) |

The choice of which solution to use depends on the specific constraints of your problem. If space is a critical concern, Morris traversal is the best option. Otherwise, the recursive or iterative stack-based approaches are generally simpler to understand and implement.