Binary Tree Inorder Traversal

Difficulty: Easy Source: NeetCode

Problem

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: []

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary Trees — Hierarchical data structure where each node has at most two children
• Recursion — Calling a function from within itself to solve subproblems
• Stack — LIFO data structure used to simulate the call stack iteratively

1. Recursive DFS

Intuition

Inorder means left → root → right. The recursive approach naturally mirrors this definition — recurse into the left subtree, visit the current node, then recurse into the right subtree. The call stack handles backtracking for free.

Algorithm

1. If the current node is null, return
2. Recurse on the left child
3. Append the current node’s value to the result
4. Recurse on the right child

Solution

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

def inorder_recursive(root):
    result = []

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

    dfs(root)
    return result

# --- helpers ---
def build_tree(values):
    """Build a tree from a level-order list. None means missing node."""
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, None, 2, 3])
print(inorder_recursive(root1))  # [1, 3, 2]

root2 = build_tree([])
print(inorder_recursive(root2))  # []

root3 = build_tree([1, 2, 3, 4, 5])
print(inorder_recursive(root3))  # [4, 2, 5, 1, 3]

Complexity

• Time: O(n) — visit every node once
• Space: O(h) — call stack depth equals tree height (O(n) worst case for skewed trees)

2. Iterative (Stack-Based)

Intuition

We simulate the recursive call stack explicitly. The idea is to keep going left, pushing nodes onto the stack. When we can’t go left anymore, pop a node (that’s the “visit” step), then pivot to its right child.

Algorithm

1. Initialize an empty stack and set curr = root
2. While curr is not null or the stack is not empty:
   • Push curr and go left until null
   • Pop from stack, record its value
   • Move curr to the popped node’s right child

Solution

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

def inorder_iterative(root):
    result = []
    stack = []
    curr = root

    while curr or stack:
        # Drill all the way left
        while curr:
            stack.append(curr)
            curr = curr.left
        # Visit the node
        curr = stack.pop()
        result.append(curr.val)
        # Pivot right
        curr = curr.right

    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, None, 2, 3])
print(inorder_iterative(root1))  # [1, 3, 2]

root2 = build_tree([])
print(inorder_iterative(root2))  # []

root3 = build_tree([1, 2, 3, 4, 5])
print(inorder_iterative(root3))  # [4, 2, 5, 1, 3]

Complexity

• Time: O(n) — every node is pushed and popped exactly once
• Space: O(h) — stack holds at most one path from root to a leaf

Common Pitfalls

Confusing traversal orders. Inorder is left→root→right. A common mistake is visiting the root before recursing left (that would be preorder). Keep the mnemonic: “in” = in the middle.

Forgetting the null base case. If you don’t guard against node is None in the recursive version, you’ll hit an AttributeError trying to access .left on None.