LeetCode 94: Binary Tree Inorder Traversal Solution in Python Explained

Problem Statement

In LeetCode 94, you’re given the root of a binary tree. Your task is to return the inorder traversal of its nodes’ values, visiting the left subtree, the root, then the right subtree. This differs from string partitioning like LeetCode 93: Restore IP Addresses, focusing on tree navigation.

Constraints

• Number of nodes: 0 <= n <= 100
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

Copy codeInput: root = [1,null,2,3]
      1
       \
        2
       /
      3
Output: [1,3,2]
Explanation: Inorder: left (none), root (1), right (3 then 2).

Copy codeInput: root = []
Output: []
Explanation: Empty tree, no nodes to traverse.

Copy codeInput: root = [1]
Output: [1]
Explanation: Single node, just the root.

These examples show the inorder sequence: left, root, right.

Understanding the Problem

How do you solve LeetCode 94: Binary Tree Inorder Traversal in Python? Take root = [1,null,2,3]. We need [1,3,2]—visit left (none), root (1), right (2’s left: 3, then 2). This isn’t a linked list reversal like LeetCode 92: Reverse Linked List II; it’s about tree traversal. We’ll use: 1. Recursive Traversal: O(n) time, O(h) space—our best solution. 2. Stack-Based Traversal: O(n) time, O(h) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Recursive Traversal Approach (Primary)

Explanation

Recursive Traversal leverages the natural structure of a binary tree, visiting the left subtree, the current node, then the right subtree in a depth-first manner. It’s the best solution due to its simplicity, readability, and alignment with inorder’s definition, making it ideal for most use cases.

For [1,null,2,3]:

• No left, visit 1.
• Right: 2, visit 2’s left (3), then 2.
• Result: [1,3,2].

Step-by-Step Example

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

Example 1: root = [1,null,2,3]

Goal: Return [1,3,2].

• Start: result = [], call inorder(root=1).
• Step 1: root = 1.
• Left: None, skip.
• Visit: Append 1, result = [1].
• Right: Call inorder(2).
• Step 2: root = 2.
• Left: Call inorder(3).
• root = 3: No left/right, append 3, result = [1,3].
• Visit: Append 2, result = [1,3,2].
• Right: None, skip.
• Finish: Return [1,3,2].

Example 2: root = []

Goal: Return [].

• Start: result = [].
• Step 1: root = None, return empty result.
• Finish: Return [].

Example 3: root = [1]

Goal: Return [1].

• Start: result = [].
• Step 1: root = 1.
• Left: None, skip.
• Visit: Append 1, result = [1].
• Right: None, skip.
• Finish: Return [1].

How the Code Works (Recursive Traversal) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def inorderTraversal(root: TreeNode) -> list[int]:
    # Line 1: Initialize result list
    result = []
    # Starts as an empty list to store node values (e.g., [])
    # Will be populated during traversal

    # Line 2: Define helper function for recursion
    def inorder(node: TreeNode):
        # node = current node being processed (e.g., root=1 initially)

        # Line 3: Base case - check if node exists
        if not node:
            # If node is None (e.g., left of 1), return without action
            # Prevents errors and stops recursion at leaf ends
            return

        # Line 4: Traverse left subtree
        inorder(node.left)
        # Recursively visits the left child (e.g., node.left=None for root=1)
        # Ensures left subtree is fully explored first

        # Line 5: Visit current node
        result.append(node.val)
        # Adds current node’s value to result (e.g., append 1, result=[1])
        # Happens after left subtree, per inorder definition

        # Line 6: Traverse right subtree
        inorder(node.right)
        # Recursively visits the right child (e.g., node.right=2 for root=1)
        # Completes the inorder sequence: left, root, right

    # Line 7: Start traversal from root
    inorder(root)
    # Initiates the process with the root node (e.g., 1)
    # Builds result list through recursive calls

    # Line 8: Return the inorder traversal
    return result
    # Returns the final list (e.g., [1,3,2] for [1,null,2,3])
    # Contains all node values in inorder sequence

This detailed explanation ensures the recursive process is clear, making it the best choice for its elegance and efficiency.

Alternative: Stack-Based Traversal Approach

Explanation

Stack-Based Traversal uses a stack to mimic recursion, pushing nodes while moving left, then popping to visit and move right. It’s a strong alternative when avoiding recursion is preferred, offering explicit control over the traversal.

For [1,null,2,3]:

• Push 1, no left, pop 1, visit 1.
• Push 2, push 3, pop 3, visit 3, pop 2, visit 2.
• Result: [1,3,2].

Step-by-Step Example (Alternative)

For [1,null,2,3]:

• Start: stack = [], result = [], curr = 1.
• Step 1: Push 1, no left, pop 1, append 1, curr = 2.
• Step 2: Push 2, push 3, no left, pop 3, append 3.
• Step 3: Pop 2, append 2, no right.
• Finish: [1,3,2].

How the Code Works (Stack-Based)

Copy codedef inorderTraversalStack(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

Complexity

• Recursive Traversal:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = tree height.
• Stack-Based Traversal:
• Time: O(n) – visits each node once.
• Space: O(h) – explicit stack size.

Efficiency Notes

Recursive Traversal is the best solution with O(n) time and O(h) space, leveraging Python’s call stack for simplicity and readability—Stack-Based Traversal matches the complexity but uses explicit memory, useful for deeper control or avoiding recursion limits.

Key Insights

• Inorder Order: Left, root, right.
• Recursion: Natural for trees.
• Stack: Mimics recursion manually.

Additional Example

For root = [1,2,3,4,5]:

Copy code    1
   / \
  2   3
 / \
4   5

• Goal: [4,2,5,1,3].
• Recursive: Left (4,2,5), root (1), right (3).

Edge Cases

• Empty Tree: [] → [].
• Single Node: [1] → [1].
• Left Skewed: [1,2,3] → [3,2,1].

Both solutions handle these seamlessly.

Final Thoughts

LeetCode 94: Binary Tree Inorder Traversal in Python is a perfect intro to tree traversal. The Recursive Traversal solution shines with its clarity and efficiency, while Stack-Based Traversal offers a hands-on alternative. Want more? Try LeetCode 144: Binary Tree Preorder Traversal for a different order or LeetCode 92: Reverse Linked List II for list challenges. Ready to practice? Solve LeetCode 94 on LeetCode with [1,null,2,3], aiming for [1,3,2]—test your skills now!