Topics › Binary Trees › Traversals

Inorder Traversal of Binary Tree

Easy TUF ID 2785 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given the root of a binary tree, return the values of its nodes in inorder: first the entire left subtree in inorder, then the node itself, then the entire right subtree in inorder. An empty tree has an empty traversal.

Constraints: between 0 and 10^5 nodes here (LeetCode uses at most 100), values are arbitrary 32-bit integers, and duplicates are allowed.

Trees are written in LeetCode’s level-order form, where null marks a missing child.

Example 1

    1
     \
      2
     /
    3
root = [1, null, 2, 3]
answer = [1, 3, 2]       // 1 has no left subtree, so it comes first; inside 2's subtree, 3 (left) precedes 2

Example 2

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
root = [1, 2, 3, 4, 5, 6, 7]
answer = [4, 2, 5, 1, 6, 3, 7]   // the root sits exactly between its left and right subtrees

Inorder is the traversal that matters most for binary search trees. In a BST every value in a node’s left subtree is smaller and every value in its right subtree is larger, so “left, node, right” lists the values in sorted order. The tree [4, 2, 6, 1, 3, 5, 7] produces [1, 2, 3, 4, 5, 6, 7].

Approach 1: Recursion

Intuition. A binary tree is either empty or a root with two subtrees, and inorder is defined in exactly those terms: inorder of the left subtree, then the root, then inorder of the right subtree. The recursive function is that sentence turned into code. A single output list is passed down so no call has to build and merge its own list.

Algorithm.

1. If the node is null, return.
2. Traverse the left subtree.
3. Append the node’s value.
4. Traverse the right subtree.

static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    inorder(root, out);
    return out;
}

private static void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;                 // empty subtree: nothing to visit
    inorder(node.left, out);                  // Left
    out.add(node.val);                        // Root
    inorder(node.right, out);                 // Right
}

Why it works. By induction on the subtree size. The empty subtree appends nothing. For a non-empty subtree, the first recursive call appends precisely the left subtree in inorder, then the root is appended, then the second call appends precisely the right subtree in inorder.

Complexity. Time O(n): one call with constant work per node, plus n + 1 calls that hit null and return. Space O(h) for the call stack, where h is the tree height: O(log n) when balanced, O(n) for a chain. A chain of 10^5 nodes can overflow Java’s default stack, which is why the next two approaches exist.

Approach 2: Iterative with a stack

Intuition. When we first meet a node we cannot output it yet: its whole left subtree must come first. So we postpone it on a stack and step left. We keep doing that until we step off the tree (cur == null). At that point the top of the stack is the deepest postponed node, and its left subtree is completely finished (either it had none, or we just finished it). We pop it, output it, and then treat its right subtree exactly like a fresh tree.

The invariant that makes this correct: the stack always holds the nodes on the current path whose left subtree is in progress and which have not been output yet, deepest on top.

Algorithm.

1. Set cur = root and start with an empty stack.
2. While cur is not null or the stack is not empty:
   • Walk left from cur, pushing every node, until cur becomes null.
   • Pop a node, append its value, and set cur to its right child.

static List<Integer> iterative(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {                 // walk down the left spine, remembering every node
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();                    // leftmost node whose left subtree is finished
        out.add(cur.val);
        cur = cur.right;                      // its right subtree is handled the same way
    }
    return out;
}

Dry run on Example 2. The stack is written bottom to top.

At step 6 the stack is empty but cur is node 3, which is why the loop condition needs both halves: cur != null || !stack.isEmpty().

Complexity. Time O(n): every node is pushed once and popped once. Space O(h): the stack holds one root-to-node path at most.

Approach 3: Morris traversal

Intuition. The stack in Approach 2 answers one question: after finishing a left subtree, which node do we return to? In inorder, the last node of cur’s left subtree is its predecessor, the rightmost node of that left subtree, and its right pointer is always null. Morris traversal borrows that pointer: before going left from cur, it sets pred.right = cur. This temporary link is called a thread. When the walk later finishes the left subtree, it is standing on pred, follows the “right” pointer, and lands back on cur with no stack involved.

So every node with a left child is reached twice. On the second arrival we can tell it is the second one because pred.right already equals cur. That second arrival is exactly when the left subtree is done, so for inorder that is when we output cur, remove the thread and go right.

Algorithm.

1. Set cur = root.
2. While cur is not null:
   • If cur.left is null: output cur and move to cur.right.
   • Otherwise find pred, the rightmost node of cur.left, stopping if pred.right == cur.
     • If pred.right is null: set pred.right = cur and move to cur.left.
     • Otherwise: set pred.right = null, output cur, and move to cur.right.

static List<Integer> morris(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            out.add(cur.val);                             // nothing on the left: visit and go right
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;                     // inorder predecessor = rightmost node of the left subtree
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {                     // first arrival: leave a thread back to cur, go left
                pred.right = cur;
                cur = cur.left;
            } else {                                      // second arrival: left subtree done, unthread and visit
                pred.right = null;
                out.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return out;
}

Dry run on the three-node tree [1, 2, 3] (2 is the left child, 3 the right child of 1).

Complexity. Time O(n): each predecessor search walks the right edges of one left subtree, and each edge is walked by at most two such searches, once to add a thread and once to remove it. Space O(1) besides the output.

The tree is modified while the loop runs and restored by the time it ends. Do not use Morris on a tree that other threads read concurrently. The Java tests re-run the recursive traversal afterwards to prove the tree is intact.

Edge cases and pitfalls

• Empty tree. All methods return an empty list; the iterative loop never starts because cur is null and the stack is empty.
• Loop condition. Using only !stack.isEmpty() stops too early (step 6 above), and using only cur != null stops as soon as a leaf without a right child is popped.
• Left-skewed chain. The output is the chain reversed, and the iterative stack grows to n entries, still fine on the heap. The tests use chains of 10^5 nodes in both directions.
• Morris predecessor search. It must stop at pred.right == cur, otherwise it follows the thread into an infinite loop. Forgetting pred.right = null leaves a cycle in the tree.
• Duplicates. Equal values are separate nodes and appear as many times as they occur.

Related problems

• Preorder Traversal visits the root before its subtrees.
• Postorder Traversal visits the root after its subtrees.
• Iterative Inorder Traversal of Binary Tree looks at the stack version more closely, including a flag-based variant.
• Morris Inorder Traversal of a Binary Tree is a full treatment of threading.
• Check if a tree is a BST or not uses the sorted-order property of inorder.
• Kth Smallest and Largest element in BST stops an inorder traversal after k nodes.
• BST iterator turns the stack version into an on-demand next().