AlgoMaster Logo

Binary Tree Inorder Traversal

Last Updated: March 29, 2026

easy
4 min read

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 produces values in sorted order, which is one reason inorder traversal is so fundamental.

The problem itself is straightforward, but it's a great vehicle for understanding three different traversal techniques: recursion, iterative with an explicit stack, and Morris traversal. Each teaches something valuable about how tree traversal actually works under the hood.

The key question is: how do we systematically visit every left subtree before processing a node, without losing track of where to go next?

Key Constraints:

  • Number of nodes in range [0, 100] — With at most 100 nodes, even the most naive approach would be instant. The real value of this problem isn't performance optimization but understanding traversal mechanics.
  • -100 <= Node.val <= 100 — Node values can be negative. This doesn't affect traversal logic, but our solution must handle negative values in the output.
  • The tree can be empty (0 nodes), so we must handle the null root case.

Approach 1: Recursive DFS

Intuition

Recursion is the natural starting point because the definition of inorder traversal is itself recursive: traverse the left subtree, visit the node, traverse the right subtree. The code practically writes itself from the definition.

Every node in the tree gets visited exactly once. At each node, we first recurse into the left child, then add the current node's value to our result, then recurse into the right child. The call stack handles all the bookkeeping of where to return to after finishing a subtree.

Algorithm

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

Example Walkthrough

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

Code

The recursive solution relies on the system call stack, which could overflow for deeply skewed trees. What if we managed the stack ourselves?

Approach 2: Iterative with Explicit Stack

Intuition

Recursion is elegant, but it hides the mechanics. When the recursive inorder function calls itself on the left child, it's really saying "I need to come back to this node later, after the left subtree is done." The call stack remembers that for us. But we can do the same thing with an explicit stack.

The idea is simple: keep pushing nodes onto the stack as you go left. When you can't go left anymore, pop a node, that's the one you should visit next (because its entire left subtree has been processed). After visiting it, move to its right child and repeat the process.

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

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

Code

Both the recursive and iterative stack approaches use O(h) extra space. Is there a way to traverse the tree without any extra space at all?

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

Intuition

Morris traversal is clever. The fundamental problem with traversing a tree without a stack is: after you finish the left subtree of some node, how do you get back to that node? With recursion or an explicit stack, the return address is saved. Without any extra storage, you need another way.

Morris traversal solves this by temporarily threading the tree. Before going into a node's left subtree, it finds the inorder predecessor, the rightmost node in the left subtree. That predecessor's right child is normally null. Morris traversal sets it to point back to the current node. Now, after finishing the left subtree, the traversal naturally follows this temporary link back to the current node. Once back, it detects the link, removes it to restore the tree, processes 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.

Example Walkthrough

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

Code