Binary Tree Inorder Traversal easy

Problem Statement

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]

Example 2

Input: root = [] Output: []

Steps

The inorder traversal of a binary tree follows the pattern: left subtree -> root -> right subtree. We need a recursive or iterative approach to traverse the tree in this order. A recursive approach is generally easier to understand, while an iterative approach (using a stack) is often more efficient in terms of space complexity for very deep trees. Here we'll show both approaches.

Explanation

Recursive Approach:

1. Base Case: If the node is None, return an empty list.
2. Recursive Step: Recursively traverse the left subtree, then add the current node's value, and finally recursively traverse the right subtree. Concatenate the results to form the inorder traversal.

Iterative Approach:

1. Initialize an empty stack and an empty result list.
2. 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 and move to its left child.
   • If the current node is None: pop a node from the stack, add its value to the result list, and move to its right child.

Code

Recursive Approach:

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

Iterative Approach:

class Solution:
    def inorderTraversal(self, root: Optional[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

Complexity

Recursive Approach:

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
• Space Complexity: O(H) in the worst case, where H is the height of the tree (due to recursive call stack). In a skewed tree, H can be N. In a balanced tree, H is log(N).

Iterative Approach:

• Time Complexity: O(N)
• Space Complexity: O(H) in the worst case (due to the stack). Again, this can be N for a skewed tree and log(N) for a balanced tree. The iterative approach generally uses less space than the recursive approach for very deep trees.

Note: TreeNode is assumed to be a class representing a node in a binary tree, with attributes val, left, and right. You would need to define this class if you are running this code (e.g., class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right). Also Optional and List are type hints from the typing module, helpful for clarity but not strictly necessary for the code to function.