Binary Tree Inorder Traversal: Left, Root, Right

Given the root of a binary tree, return the inorder traversal of its node values. Inorder means you visit the left subtree first, then the current node, then the right subtree.

This is LeetCode 94: Binary Tree Inorder Traversal. It is one of the first tree problems you should solve because it introduces two foundational techniques: recursive tree traversal and iterative stack-based traversal. Both show up constantly in harder tree problems.

Example: given root = [1, null, 2, 3], the inorder traversal is [1, 3, 2].

Why this problem matters

Inorder traversal is one of the three standard depth-first traversal orders for binary trees (preorder, inorder, postorder). Each one follows the same recursive structure but changes when the current node gets processed relative to its children.

What makes inorder special is its relationship to binary search trees. An inorder traversal of a BST produces values in sorted order. This property is the key to problems like Validate BST (LeetCode 98) and Kth Smallest Element in a BST (LeetCode 230). If you can write inorder traversal from memory, you already have the core of those solutions.

Approach 1: Recursive

The recursive solution maps directly to the definition. Visit left, process current node, visit right.

def inorder_traversal(root):
    result = []

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

    dfs(root)
    return result

The base case is if node is None: return. That stops the recursion at leaves. The three lines after the base case are the entire algorithm: recurse left, record the value, recurse right. The order of those three lines is what makes it "inorder." Swap them and you get preorder or postorder.

Approach 2: Iterative with a stack

The iterative version replaces the call stack with an explicit stack. This is important to know because interviewers sometimes ask for the iterative solution specifically, and some problems (like BST iterator) require it.

def inorder_traversal(root):
    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

The idea: keep pushing left children onto the stack until you hit None. Then pop a node, add its value, and move to its right child. Repeat. The inner while curr loop handles "go as far left as possible." The pop-and-go-right step handles "process current, then visit right subtree."

Iterative walkthrough

Let's trace the iterative approach on the example tree [1, null, 2, 3].

The stack simulates what the call stack does in the recursive version. Each push is like entering a recursive call. Each pop is like returning from one. The key insight is that you always go left first, and you only process a node (add it to output) when you pop it from the stack.

Complexity analysis

Time is O(n) for both approaches. Every node is visited exactly once.

Space is O(n) in the worst case for both. The recursive version uses O(h) call stack space where h is the height of the tree. The iterative version uses O(h) explicit stack space. For a balanced tree, h = log(n). For a completely skewed tree (every node only has a left child or only a right child), h = n, which gives O(n) space. Since h can be as large as n, the worst-case space for both is O(n).

Edge cases

• Empty tree (root is None): return an empty list. Both solutions handle this. The recursive version hits the base case immediately. The iterative version never enters the while loop.
• Single node (no children): return [root.val]. The recursive version calls dfs(None) twice and appends the value once. The iterative version pushes the root, pops it, adds its value, and curr.right is None so the loop ends.
• Left-skewed tree (every node only has a left child): the tree looks like a linked list going left. The iterative version pushes all n nodes onto the stack in the inner while loop, then pops them one by one. Output order is bottom to top.
• Right-skewed tree (every node only has a right child): the inner while loop does nothing (root has no left child). You pop the root, add it, move right, pop, add, move right. The stack never holds more than one element at a time.

The building blocks

This problem teaches two reusable building blocks:

1. Recursive tree traversal. The pattern of if node is None: return followed by recursive calls on node.left and node.right is the foundation of nearly every tree problem. You will use this skeleton in Maximum Depth, Path Sum, Symmetric Tree, and many others. The only thing that changes is what you do at each node and what you return.

2. Iterative stack-based traversal. The while curr or stack loop with "push left, pop, go right" is the iterative equivalent of inorder recursion. This pattern is required for problems where you need fine-grained control over the traversal, like BST Iterator (LeetCode 173) or recovering a BST. It also avoids stack overflow for extremely deep trees.

Both blocks are worth memorizing independently. The recursive version is simpler and should be your default. The iterative version is what you reach for when the problem demands it.

From understanding to recall

You now understand two ways to traverse a binary tree in order. The recursive version is three lines inside a helper function. The iterative version is a while loop with a stack, pushing left until you cannot, then popping and going right.

But understanding is not the same as being able to write it cold. In an interview, you will not have this post open. You need to recall the inner while loop that pushes left children, the pop that processes the node, and the curr = curr.right that shifts to the right subtree.

Spaced repetition builds that recall. You type the solution from scratch after one day, then three days, then a week. Each time, you reconstruct the stack loop from memory. After a few rounds, the iterative inorder pattern becomes automatic. You stop thinking about it and just write it.

These two building blocks (recursive traversal and iterative stack-based traversal) appear in dozens of tree problems. Drilling them individually is far more effective than solving random tree problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - The best starting point for recursive tree traversal, using the same DFS skeleton
• Validate Binary Search Tree - Uses inorder traversal as one of its two solution approaches