Free lesson · DSA Mastery - Interview Prep, End to End

Binary Tree Inorder Traversal

Medium8 min readdsabinary-tree

Binary Tree Inorder Traversal

Binary Tree Inorder Traversal opens the In Order sub-group with the left-node-right traversal: recurse into the left subtree first, then visit the current node, then the right subtree. Its defining property is the engine for the whole sub-group: on a binary search tree, inorder visits values in sorted ascending order. That single fact drives BST validation, minimum-difference queries, kth-smallest lookups, and more. We present three forms, mirroring the preorder opener: the trivial recursion, the iterative stack version (which makes the "go left, visit, go right" rhythm explicit), and Morris traversal (O(1) extra space via temporary threading).

The insight: inorder differs from preorder only in where the visit step sits - between the two recursive calls instead of before them. For the iterative version, you push left children until you hit null, then pop-and-visit, then turn right. For Morris, you thread the in-order predecessor to the current node so you can return after finishing the left subtree without a stack - visiting the node when you remove the thread.

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

Example 3:

Input:  root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]

Constraints:

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

Follow-up: Recursive solution is trivial, could you do it iteratively?

Approaches Overview

#	Approach	Time	Space	Verdict
1	Recursion	O(n)	O(h)	Simplest
2	Iterative with stack	O(n)	O(h)	Answers the follow-up
3	Morris traversal	O(n)	O(1) extra	Constant space

All visit every node once - O(n). Recursion is trivial but uses O(h) stack. The iterative version uses an explicit stack (also O(h)) and is the expected follow-up answer. Morris threading achieves O(1) extra space by temporarily rewiring pointers.

Approach 1: Recursion - Simplest

The Idea

Recurse left, record the node's value, recurse right. The "node between the recursions" placement is what makes it inorder.

Logic Flowchart

graph TD
    A["inorder(node)"] --> B{"node == null?"}
    B -->|Yes| C["return"]
    B -->|No| D["inorder(left)"]
    D --> E["visit node (record val)"]
    E --> F["inorder(right)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows recursive inorder. We recurse into the left subtree, then record the current node's value, then recurse into the right subtree.

Code

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

private static void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);    // left FIRST
    result.add(node.val);          // then visit node
    inorder(node.right, result);   // then right
}

This Java code recurses into the left subtree, records the current node's value, then recurses into the right subtree, producing left-node-right order.

Complexity

Time: O(n). Space: O(h) recursion stack.

Approach 2: Iterative with Stack - Answers the Follow-up

The Idea

Use an explicit stack. From the current node, push it and keep moving left, pushing every node, until you reach null. Then pop a node, record it (this is the leftmost unvisited node), and move to its right child, repeating the push-left process. This reproduces left-node-right order.

Logic Flowchart

graph TD
    A["stack = []; cur = root; result = []"] --> B{"cur != null OR stack not empty?"}
    B -->|No| C["return result"]
    B -->|Yes| D{"cur != null?"}
    D -->|Yes| E["push cur; cur = cur.left"]
    D -->|No| F["cur = pop; result.add(cur.val); cur = cur.right"]
    E --> B
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows iterative inorder. We push nodes while moving left until null, then pop and record a node before turning to its right child, repeating until both the stack is empty and the current pointer is null.

Code

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {           // dive left, stacking the path
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();              // leftmost unvisited node
        result.add(cur.val);            // visit
        cur = cur.right;                // then explore its right subtree
    }
    return result;
}

// Usage:
// inorderTraversal([1,null,2,3]) -> [1,3,2]

This Java code pushes nodes while diving left, then pops and records the leftmost node before moving to its right child, looping until the stack is empty and the pointer is null.

Step-by-Step Walkthrough

A frame-by-frame trace on root = [1,null,2,3] (1 has right child 2; 2 has left child 3):

graph LR
    F0["cur=1: push 1, go left → null. stack=[1]"]
    F1["pop 1 → result=[1]; cur=1.right=2. push 2, go left to 3, push 3, left→null"]
    F2["pop 3 → result=[1,3]; cur=3.right=null"]
    F3["pop 2 → result=[1,3,2]; cur=null. done"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traverses one with a right child two, which has a left child three. We record one, then dive into two's left child three and record it, then record two, giving one, three, two.

Result: [1,3,2].

Complexity

Time: O(n). Space: O(h) stack.

Approach 3: Morris Traversal - Constant Space

The Idea

Walk the tree using O(1) extra space via threading. For each node cur: if it has no left child, record it and move right. Otherwise find its in-order predecessor (rightmost node of the left subtree); if that predecessor's right is null, thread it to cur and move left (do not record yet); if the predecessor's right already points to cur, the left subtree is finished - record cur now (inorder), unthread, and move right. The visit happens when removing the thread, which is what distinguishes Morris inorder from Morris preorder.

Logic Flowchart

graph TD
    A["cur = root"] --> B{"cur != null?"}
    B -->|No| C["return result"]
    B -->|Yes| D{"cur.left == null?"}
    D -->|Yes| E["record cur; cur = cur.right"]
    D -->|No| F["pred = rightmost of cur.left"]
    F --> G{"pred.right == null?"}
    G -->|Yes| H["pred.right = cur; cur = cur.left (no visit yet)"]
    G -->|No| I["pred.right = null; record cur (inorder); cur = cur.right"]
    E --> B
    H --> B
    I --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Morris inorder. A node with no left child is recorded before moving right. Otherwise we thread the left subtree's rightmost node to the current node and go left without recording; when we return via that thread, we record the current node and go right.

Code

public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            result.add(cur.val);                 // no left subtree: visit, go right
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;                // thread; descend left WITHOUT visiting
                cur = cur.left;
            } else {
                pred.right = null;               // unthread
                result.add(cur.val);             // INORDER: visit after left subtree done
                cur = cur.right;
            }
        }
    }
    return result;
}

This Java code performs Morris inorder. Nodes without a left child are recorded and we move right. Otherwise we thread the left subtree's rightmost node to the current node and descend left; on returning via the thread we unthread, record the current node, and move right.

Complexity

Time: O(n). Space: O(1) extra.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Recursion	O(n)	O(h)	Left, node, right	Simplest
Iterative stack	O(n)	O(h)	Dive left, pop-visit, turn right	Follow-up answer
Morris	O(n)	O(1) extra	Thread predecessor, visit on unthread	Constant space required

All are O(n) time. Recursion is cleanest; the iterative stack is the standard follow-up; Morris is the O(1)-space technique. Note the one-line difference between Morris preorder and Morris inorder: when you record the node (on thread creation for preorder, on thread removal for inorder).

Variations & Follow-ups

Why does inorder produce sorted output on a BST?

A binary search tree's invariant is that every node's left subtree holds smaller values and its right subtree holds larger ones. Inorder visits left subtree, then node, then right subtree - so for any node, all smaller values (left) are emitted before it and all larger values (right) after it. Applied recursively, this yields the values in strictly ascending order. This is the property the entire In Order sub-group exploits.

How does the iterative version's stack encode the recursion?

The stack holds the chain of ancestors whose right subtrees haven't been explored yet - exactly the frames a recursive call stack would hold. Diving left and pushing mirrors the left-recursion descending; popping and visiting corresponds to a recursive call returning to its "visit node" step; turning right starts the right-recursion. The explicit stack is a faithful manual simulation of the call stack, which is why it has the same O(h) space.

What distinguishes Morris inorder from Morris preorder?

The threading machinery is identical; only the timing of the visit differs. Preorder records the node when it first creates the thread (before going left), because preorder visits the node before its left subtree. Inorder records the node when it removes the thread (after the left subtree is fully traversed), because inorder visits the node between its subtrees. That single placement change converts one into the other.

When is the iterative version preferable to recursion?

When recursion depth is a risk - a degenerate tree of height ~n could overflow the call stack for large n, whereas the explicit stack lives on the heap and tolerates greater depth. The iterative form is also handy when you need to pause mid-traversal (e.g., the BST Iterator problem later in this sub-group is essentially this iterative inorder, exposed one step at a time). For the small constraint here (≤100 nodes) all three are equally safe.

What about edge cases?

Empty tree (Example 2): Empty result.
Single node: [root.val].
Left-skewed chain: Visited bottom-to-top: [deepest, …, root].
Right-skewed chain: Visited top-to-bottom: [root, …, deepest].

Common Interview Pitfalls

Recording at the wrong time. Inorder visits between the recursions; recording before or after gives pre/postorder.
Iterative loop condition. Continue while cur != null or the stack is non-empty; checking only one ends early.
Morris: not unthreading. Failing to restore pred.right = null corrupts the tree and risks an infinite loop.
Morris: visiting on thread creation. That's preorder; for inorder, visit on thread removal.

Why This Topic Matters

Binary Tree Inorder Traversal establishes the left-node-right order and its three realizations, but its real significance is the sorted-order guarantee on a BST - the property every remaining problem in this sub-group leans on. The iterative stack form also directly seeds the BST Iterator design later, and the Morris timing contrast deepens understanding of how a single placement choice defines each traversal.

The next topic, Minimum Distance Between BST Nodes, is the first direct application: find the smallest absolute difference between the values of any two nodes in a BST. Because an inorder traversal of a BST yields sorted values, the minimum difference must occur between adjacent values in that sorted sequence - so a single inorder pass tracking the previous value and the running minimum gap solves it in O(n). It's the cleanest demonstration of "inorder turns a BST into a sorted list, and sorted lists make difference problems trivial."

Back to DSA Mastery - Interview Prep, End to End