Inorder Traversal Explained: Recursive, Iterative & Morris Methods

Imagine you need to print all values in a binary search tree in sorted order. How would you do it efficiently? You could copy everything into an array and sort it, but that feels wasteful. There's a cleaner way—a tree traversal algorithm that visits nodes in exactly the right sequence. That algorithm is inorder traversal, and it's one of the most fundamental techniques in computer science.

In this guide, I'll walk you through everything you need to know about this essential binary tree traversal method. We'll cover the recursive approach (which is the foundation), the iterative version using a stack (a favorite in coding interviews), and the advanced Morris traversal that achieves O(1) space. I'll also show you why inorder traversal is so critical for binary search trees and include code examples in Python, Java, and C++.

Let's get started.

What is Inorder Traversal in a Binary Tree?

Inorder traversal is a depth-first search technique where you visit nodes in a specific order: left subtree, then root, then right subtree. It's called "inorder" because the root node is processed in between its left and right subtrees.

The Left-Root-Right Rule

The recursive definition is elegantly simple:

1. Traverse the left subtree
2. Visit the root node
3. Traverse the right subtree

Consider this sample tree:

    A
   / \
  B   C
 / \ / \
D  E F  G

Applying the left-root-right rule, the inorder traversal sequence is: D, B, E, A, F, C, G.

Notice how we go all the way down the left side first. We visit D (leftmost node), then backtrack to B, then go to E, then back to A, and so on. This "go deep first" behavior is what makes it a depth-first search.

Inorder vs. Preorder vs. Postorder: A Quick Comparison

The three DFS traversals differ only in when the root is visited relative to its subtrees:

What makes inorder unique is that for a binary search tree, this order produces values in ascending sequence. That single property makes it invaluable—we'll dive deep into that later.

Recursive Inorder Traversal: The Foundation

If you're new to tree traversals, recursion is where you should start. It's the most intuitive implementation, and once you understand it, the iterative version becomes much easier to grasp.

How Recursion Works for Inorder Traversal

The recursive approach leverages the call stack implicitly. Here's the logic:

• Base case: If the node is null, return.
• Recursive case: Call the function on the left child, visit the current node, then call the function on the right child.

Let me trace through a small tree to show you what happens under the hood:

  A
 / \
B   C

When we call inorderTraversal(A):

1. A is not null, so we call inorderTraversal(A.left) → inorderTraversal(B)
2. B is not null, so we call inorderTraversal(B.left) → inorderTraversal(null) → returns immediately
3. We visit B → output: B
4. We call inorderTraversal(B.right) → inorderTraversal(null) → returns
5. Back in A's frame, we visit A → output: B, A
6. We call inorderTraversal(A.right) → inorderTraversal(C)
7. C is not null, so we call inorderTraversal(C.left) → returns
8. We visit C → output: B, A, C

The recursion call stack grows as we descend into the left subtree, then unwinds as we visit nodes and move to the right. This is a classic example of depth-first exploration.

Recursive Inorder Traversal Code Examples

Here's the implementation in three popular languages. First, let's define the tree node structure:

Python:

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

def inorder_traversal(root):
    """Returns a list of node values in inorder sequence."""
    result = []
    
    def traverse(node):
        if node is None:
            return
        traverse(node.left)      # 1. Left subtree
        result.append(node.val)  # 2. Visit root
        traverse(node.right)     # 3. Right subtree
    
    traverse(root)
    return result

Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    private List<Integer> result = new ArrayList<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        traverse(root);
        return result;
    }
    
    private void traverse(TreeNode node) {
        if (node == null) return;
        traverse(node.left);       // 1. Left subtree
        result.add(node.val);      // 2. Visit root
        traverse(node.right);      // 3. Right subtree
    }
}

C++:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;
    }
    
private:
    void traverse(TreeNode* node, vector<int>& result) {
        if (!node) return;
        traverse(node->left, result);       // 1. Left subtree
        result.push_back(node->val);        // 2. Visit root
        traverse(node->right, result);      // 3. Right subtree
    }
};

For the sample tree [1, null, 2, 3] (root 1, right child 2, left child 3), the output is [1, 3, 2].

Iterative Inorder Traversal Using a Stack

Recursion is elegant, but it has a hidden cost: the call stack. For deeply skewed trees, recursion can cause a stack overflow. That's where the iterative approach shines.

Why Use an Iterative Approach?

Here's the trade-off I've seen play out countless times in real projects and interviews:

Recursive approach:

• ✅ Simple, readable, mirrors the mathematical definition
• ❌ Uses O(h) call stack space (h = tree height)
• ❌ Risk of stack overflow on very deep trees

Iterative approach:

• ✅ Explicit control over memory usage
• ✅ No risk of stack overflow
• ✅ Often expected in coding interviews
• ❌ Slightly more complex to write

In my experience, interviewers frequently ask for the iterative version specifically to test whether you understand how recursion works under the hood. The explicit stack simulates the call stack, which shows deeper understanding.

Step-by-Step Algorithm for Iterative Inorder Traversal

The algorithm uses an explicit stack to simulate the recursion:

1. Initialize an empty stack and set current = root
2. While current is not null OR stack is not empty:
   • While current is not null: push current onto stack, move to current.left
   • Pop the top node from stack, visit it
   • Set current = popped_node.right

Let me walk through this with a concrete example:

    A
   / \
  B   C
 / \
D   E

Iterative Inorder Traversal Code Examples

Python:

def inorder_traversal_iterative(root):
    """Iterative inorder traversal using an explicit stack."""
    result = []
    stack = []
    current = root
    
    while current is not None or stack:
        # Reach the leftmost node of the current subtree
        while current is not None:
            stack.append(current)
            current = current.left
        
        # current is None, pop and visit
        current = stack.pop()
        result.append(current.val)
        
        # Move to the right subtree
        current = current.right
    
    return result

Java:

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // Reach the leftmost node
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    
    return result;
}

C++:

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    TreeNode* current = root;
    
    while (current != nullptr || !stk.empty()) {
        // Reach the leftmost node
        while (current != nullptr) {
            stk.push(current);
            current = current->left;
        }
        
        current = stk.top();
        stk.pop();
        result.push_back(current->val);
        current = current->right;
    }
    
    return result;
}

Morris Traversal: Inorder Traversal Without Recursion or Stack

Now we get to the advanced stuff. Morris traversal is a clever technique that achieves O(1) space complexity—no recursion, no explicit stack. It's not something you'll use every day, but understanding it deepens your grasp of tree structures.

The Magic of O(1) Space Complexity

The core idea behind Morris traversal is to temporarily modify the tree by creating "threads"—links from a node to its inorder successor. These threads allow us to backtrack without a stack.

Here's the intuition: when we finish traversing a left subtree, we need to know where to go next. Normally, we'd use a stack to remember. Morris traversal instead creates a temporary link from the rightmost node of the left subtree back to the current node. After visiting that rightmost node, we follow the thread to the current node, then remove the thread to restore the tree.

The algorithm works like this:

1. Initialize current = root
2. While current is not null:
   • If current.left is null: visit current, move to current.right
   • Else: find the inorder predecessor of current (the rightmost node in current.left)
     • If predecessor's right is null: set predecessor.right = current (create thread), move to current.left
     • If predecessor's right is current: remove the thread (set predecessor.right = null), visit current, move to current.right

The beauty is that we're using the tree's own structure to store backtracking information. It's like leaving breadcrumbs that we clean up as we go.

Morris Traversal Algorithm and Code

Here's a Python implementation:

def inorder_traversal_morris(root):
    """Morris traversal: inorder without recursion or stack, O(1) space."""
    result = []
    current = root
    
    while current is not None:
        if current.left is None:
            # No left subtree, visit current and go right
            result.append(current.val)
            current = current.right
        else:
            # Find the inorder predecessor
            predecessor = current.left
            while predecessor.right is not None and predecessor.right != current:
                predecessor = predecessor.right
            
            if predecessor.right is None:
                # Create thread to current, go left
                predecessor.right = current
                current = current.left
            else:
                # Thread already exists, remove it and visit current
                predecessor.right = None
                result.append(current.val)
                current = current.right
    
    return result

The trade-off is clear: O(1) space comes at the cost of temporarily modifying the tree. In single-threaded environments or when the tree is read-only, this isn't suitable. But in scenarios where memory is tight—think embedded systems or massive trees—Morris traversal is a lifesaver.

Why Inorder Traversal is Crucial for Binary Search Trees

If there's one thing you take away from this article, let it be this: inorder traversal and binary search trees are a match made in heaven.

Inorder Traversal Produces Sorted Output

In a binary search tree (BST), every node in the left subtree has a value less than the root, and every node in the right subtree has a value greater than the root. This property holds recursively for every subtree.

When you perform an inorder traversal (left → root → right), you're visiting nodes in exactly the order: all smaller values first, then the root, then all larger values. Recursively, this means you visit values in ascending order.

Here's a BST example:

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

The inorder traversal gives us: 1, 3, 4, 6, 7, 8, 10, 13, 14 — perfectly sorted.

This isn't a coincidence. It's a direct consequence of the BST invariant. I've used this property more times than I can count to debug BST implementations—if the inorder output isn't sorted, something's wrong with the tree structure.

Practical Applications: Validating a BST and Finding the k-th Smallest Element

Let me show you two practical applications that I've implemented in production systems.

1. Validating a BST

The simplest way to check if a binary tree is a valid BST is to perform an inorder traversal and verify the output is strictly increasing:

def is_valid_bst(root):
    """Check if a binary tree is a valid BST using inorder traversal."""
    prev = [float('-inf')]  # Use a list for mutable closure
    
    def traverse(node):
        if node is None:
            return True
        
        # Check left subtree
        if not traverse(node.left):
            return False
        
        # Check current node against previous value
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        
        # Check right subtree
        return traverse(node.right)
    
    return traverse(root)

2. Finding the k-th Smallest Element

Since inorder traversal visits nodes in sorted order, the k-th node visited is the k-th smallest element:

def kth_smallest(root, k):
    """Find the k-th smallest element in a BST (1-indexed)."""
    count = [0]
    result = [None]
    
    def traverse(node):
        if node is None or result[0] is not None:
            return
        
        traverse(node.left)
        
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        
        traverse(node.right)
    
    traverse(root)
    return result[0]

Other applications include converting a BST to a sorted array, finding the median of a BST, and merging two BSTs into a sorted list.

Inorder Traversal: Time and Space Complexity Analysis

Let's break down the complexity of each method. This is the kind of analysis that separates a solid understanding from a superficial one.

Time Complexity: O(n)

All three methods—recursive, iterative, and Morris—visit each node exactly once. Each visit involves constant-time operations (comparisons, pointer updates, or value appends). Therefore, the time complexity is O(n), where n is the number of nodes.

There's no way to do better than O(n) for a full traversal. You have to look at every node at least once.

Space Complexity: Recursive vs. Iterative vs. Morris

This is where the methods diverge significantly:

In practice, I've seen the recursive approach fail on trees with tens of thousands of nodes when the tree is highly unbalanced. The iterative approach handles those cases gracefully. Morris traversal, while clever, is rarely necessary unless you're working with severe memory constraints.

Frequently Asked Questions

Why is inorder traversal of a binary search tree sorted?

In a BST, all values in the left subtree are less than the root, and all values in the right subtree are greater. Since inorder visits the left subtree first, then the root, then the right subtree, it naturally visits nodes in ascending order. This property holds recursively at every level of the tree.

How to do inorder traversal without recursion?

Use an explicit stack. The algorithm: push all left children onto the stack, pop and visit the top node, then move to its right child and repeat. Alternatively, use Morris traversal, which achieves O(1) space by temporarily modifying the tree structure.

What is the difference between inorder and preorder traversal?

Inorder traversal follows left-root-right order, while preorder follows root-left-right. For the tree A(B, C) (root A, left B, right C), inorder gives B, A, C and preorder gives A, B, C. The key difference is when the root is processed: in the middle (inorder) versus first (preorder).

Is inorder traversal depth-first search?

Yes. Inorder traversal is a specific type of depth-first search (DFS) algorithm. It explores as deep as possible along each branch before backtracking—specifically, it goes all the way down the left subtree before visiting the root and then exploring the right subtree.

Conclusion

We've covered a lot of ground. Let me recap the key takeaways:

• Recursive inorder traversal is the most intuitive approach—simple, readable, and perfect for learning. It uses O(h) space for the call stack.
• Iterative inorder traversal with an explicit stack eliminates the risk of stack overflow and is a common interview question. Same O(h) space, but with explicit control.
• Morris traversal achieves O(1) space by temporarily modifying the tree structure. It's advanced but demonstrates deep understanding.

All three methods run in O(n) time. The choice depends on your constraints: readability, memory, or the need to avoid recursion.

Most importantly, remember why inorder traversal matters: for binary search trees, it produces sorted output. This single property powers BST validation, k-th smallest element queries, and countless other algorithms.

Now that you've mastered inorder traversal, test your skills by solving the "Binary Tree Inorder Traversal" problem on LeetCode (Problem 94). Try implementing all three methods and compare their performance. You might be surprised by how much faster the iterative version runs on deeply skewed trees—I know I was the first time I benchmarked it.