AlgoMaster Logo

Binary Tree Inorder Traversal

easyFrequency9 min readUpdated June 23, 2026

Understanding the Problem

We need to traverse a binary tree in inorder order and return the node values as a list. Inorder means: visit the left subtree first, then the current node, then the right subtree. For a binary search tree, this visits the values in sorted order.

Recursion solves the problem in a few lines. The follow-up question (can you do it iteratively?) is what gives the problem depth, and pushing further to O(1) extra space leads to Morris traversal, which needs no stack at all. Every version has to solve the same subproblem: after finishing a node's left subtree, the traversal must return to that node without having lost track of it.

Key Constraints:

  • Number of nodes in range [0, 100]: Performance is not a concern at this size. The constraint that shapes the solutions is the follow-up: implement the traversal iteratively, and ideally in O(1) extra space.
  • -100 <= Node.val <= 100: Values play no role in the traversal; only the tree structure does.
  • The tree can be empty (0 nodes), so every solution must handle a null root.

Approach 1: Recursive DFS

Intuition

The definition of inorder traversal is itself recursive: traverse the left subtree, visit the node, traverse the right subtree. The recursive solution is a direct transcription of that definition.

Every node is visited exactly once. At each node, the function first recurses into the left child, then appends the node's value to the result, then recurses into the right child. The call stack records where to resume after each recursive call returns, so the return-to-parent problem is handled for us. A null root needs no special case: the helper's base case covers it, and the result stays empty.

Algorithm

  1. Create an empty list called result.
  2. Define a recursive helper inorder(node):
    • If node is null, return.
    • Recurse on node.left.
    • Append node.val to result.
    • Recurse on node.right.
  3. Call inorder(root) and return result.

Example Walkthrough

root
1Start: call inorder(1)
1current23
result
1Result list starts empty
1/5

Code

The recursion depends on the system call stack, which can overflow on a deeply skewed tree. The next approach manages the stack explicitly.

Approach 2: Iterative with Explicit Stack

Intuition

When the recursive inorder function calls itself on the left child, the call stack saves the current node so execution can resume there after the left subtree finishes. An explicit stack can store the same information.

Push nodes onto the stack while moving left. When there is no left child to move to, pop a node: its entire left subtree has been processed, so it is the next node in inorder order. Record its value, then move to its right child and repeat. Each operation maps one-to-one onto the recursion: pushing a node and moving left is the call inorder(node.left), popping and recording is the return from that call followed by the visit, and moving right is the call inorder(node.right).

Algorithm

  1. Create an empty list result and an empty stack.
  2. Set current to root.
  3. While current is not null or the stack is not empty:
    • While current is not null, push current onto the stack and move to current.left.
    • Pop the top node from the stack into current.
    • Append current.val to result.
    • Move current to current.right.
  4. Return result.

Example Walkthrough

root
1Start: current = 1, stack = []
1current23
stack
1Stack starts empty
1/6

Code

This loop is shaped specifically for inorder order; producing preorder or postorder requires restructuring it. The next approach trades a slightly larger stack for a single template that produces all three orders.

Approach 3: Iterative with Visited Flags

Intuition

Approach 2 distinguishes two situations implicitly: encountering a node for the first time (keep going left) and returning to it after its left subtree (record it). Storing that distinction on the stack makes the code uniform. Each stack entry is a pair of a node and a visited flag.

Popping an unvisited node records nothing. Instead, it schedules three entries: the right child, the node itself with visited set, and the left child, pushed in that order. Because the stack is last-in-first-out, they are processed in reverse: left subtree first, then the node, then the right subtree, which is inorder order. Popping a visited node means its left subtree is already done, so its value goes to the result.

The push order is the entire definition of the traversal. Pushing right child, left child, then the flagged node yields preorder; pushing the flagged node, right child, then left child yields postorder. Approach 2 cannot be adapted that mechanically.

Algorithm

  1. Create an empty list result and a stack containing the single entry (root, false).
  2. While the stack is not empty:
    • Pop (node, visited).
    • If node is null, skip it.
    • If visited is true, append node.val to result.
    • Otherwise, push (node.right, false), then (node, true), then (node.left, false).
  3. Return result.

Example Walkthrough

In the stack below, an entry marked * has its visited flag set.

root
1Start: push (1, unvisited)
1current23
stack
1Stack starts with (1, unvisited)
1
Top
1/8

Code

All three approaches so far need O(h) space for a stack. Morris traversal removes the stack entirely by storing the return path inside the tree.

Approach 4: Morris Traversal (O(1) Space)

Intuition

Without a stack, the unsolved problem is the return trip: after finishing the left subtree of a node, the traversal has to get back to that node, and nothing has recorded where it came from.

Morris traversal stores the return path in the tree itself. Before descending into a node's left subtree, it finds the inorder predecessor: the rightmost node in that left subtree. The predecessor is the last node visited before the traversal should return, and its right pointer is null, so Morris traversal points it back at the current node. When the traversal later finishes the left subtree, it ends at the predecessor, moves right, and arrives back at the current node through this temporary thread. Finding the thread already in place is also the signal that the left subtree is done: the traversal removes the thread to restore the tree, records the current node, and moves right.

Algorithm

  1. Set current to root.
  2. While current is not null:
    • If current.left is null: append current.val to result, move to current.right.
    • Else: find the inorder predecessor (go to current.left, then keep going right until you find a node whose right child is null or points back to current).
      • If the predecessor's right child is null: set predecessor.right = current (create thread), move to current.left.
      • If the predecessor's right child is current: set predecessor.right = null (remove thread), append current.val to result, move to current.right.
  3. Return result.

Morris traversal modifies the tree while it runs. Every thread is removed when the traversal passes back through it, so the tree is fully restored by the time the function returns. The temporary mutation still rules the approach out when another thread reads the tree concurrently, or when the input must not be modified even transiently. In those cases, Approach 2 is the standard fallback.

Example Walkthrough

root
1Start: current = 4. Find predecessor (3), create thread 3->4
4current213thread->4657
result
1Result starts empty. Creating thread 3->4
1/10

Code

The threading technique extends beyond inorder traversal. Recording a node's value when its thread is created (instead of when the thread is removed) produces a preorder Morris traversal with the same O(1) space bound. A postorder variant exists as well, though it is more involved: it visits nodes by reversing the right spine of each left subtree.