☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Morris Inorder Traversal

Hard TUF ID 139 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Return the inorder traversal of a binary tree (left subtree, node, right subtree) as a list of values, using only O(1) extra memory besides the output list: no recursion and no explicit stack. You may modify the tree while the traversal runs, but it must be exactly as it was when the method returns.

Constraints (LeetCode 94, whose follow-up asks for this): up to 100 nodes, values in [-100, 100]. The real requirement is the memory bound; the Java file also runs a 100000-node tree and checks that the tree is unchanged afterwards.

Example 1

        1
       / \
      2   3
     / \   \
    4   5   6
answer = [4, 2, 5, 1, 3, 6]

The left subtree of 1 gives 4, 2, 5, then 1, then the right subtree gives 3, 6.

Example 2

root = [1, null, 2, 3]      // 1 has a right child 2, and 2 has a left child 3
answer = [1, 3, 2]

Approach 1: Recursion

Intuition. Inorder is defined recursively, so the simplest correct solution follows the definition: traverse the left subtree, record the node, traverse the right subtree. It is the baseline the other approaches must match, but it uses the call stack, which is O(h) memory.

Algorithm.

  1. If the node is null, return.
  2. Recurse left, append the node’s value, recurse right.
static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    inorder(root, out);
    return out;
}

static void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

Complexity. Time O(n), each node is visited once. Space O(h) for the call stack, where h is the height: O(log n) for a balanced tree, O(n) for a chain.

Approach 2: Explicit stack

Intuition. Replace the call stack with our own stack. Push the whole left spine; the top node then has a finished left side, so pop it, record it, and continue with its right child. This avoids recursion but still stores up to h nodes, so it does not meet the O(1) bound.

Algorithm.

  1. cur = root. While cur is not null or the stack is not empty:
  2. Push cur and move left until cur is null.
  3. Pop, record, set cur to the popped node’s 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) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    return out;
}

Complexity. Time O(n), each node is pushed and popped once. Space O(h) for the stack.

Approach 3: Morris traversal

Intuition. Why do we need a stack at all? Only to find our way back up to a node after finishing its left subtree. Ask where that left subtree’s traversal ends: at its rightmost node, which is exactly the inorder predecessor of the current node. Being the rightmost node, its right pointer is null, which is an unused slot.

Morris traversal borrows that slot. Before descending into the left subtree of cur, it sets pred.right = cur. This temporary link is called a thread. When the traversal later finishes the left subtree, it reaches pred and simply follows right as usual, which carries it back to cur. No stack is needed because the path back up is stored inside the tree itself.

That means every node with a left child is reached twice, and we need to tell the two arrivals apart. We look for the predecessor again. If pred.right is null, this is the first arrival: plant the thread and go left. If pred.right == cur, we came back through the thread, so the left subtree is done: remove the thread (restoring the tree), record cur, and go right. A node without a left child has nothing to wait for, so it is recorded immediately and we go right; that right may be a real child or a thread leading back to an ancestor.

Algorithm.

  1. cur = root.
  2. While cur != null:
    • If cur.left == null: record cur, set cur = cur.right.
    • Otherwise let pred be the rightmost node of cur.left, stopping early if pred.right == cur.
      • If pred.right == null (first arrival): set pred.right = cur, then cur = cur.left.
      • Otherwise (second arrival): set pred.right = null, record cur, then cur = cur.right.
static List<Integer> morris(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {                  // nothing to the left: visit and move on
            out.add(cur.val);
            cur = cur.right;                     // may be a real child or a thread back to an ancestor
            continue;
        }
        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 visit of cur: plant the thread, go left
            pred.right = cur;
            cur = cur.left;
        } else {                                 // came back through the thread: left side is done
            pred.right = null;                   // restore the tree
            out.add(cur.val);
            cur = cur.right;
        }
    }
    return out;
}

Dry run on Example 1:

cur situation action output so far
1 pred = 5, no thread thread 5 → 1, go left  
2 pred = 4, no thread thread 4 → 2, go left  
4 no left child record, follow right (thread) to 2 4
2 pred = 4, thread found remove thread, record, go right 4, 2
5 no left child record, follow right (thread) to 1 4, 2, 5
1 pred = 5, thread found remove thread, record, go right 4, 2, 5, 1
3 no left child record, go right 4, 2, 5, 1, 3
6 no left child record, go right (null) 4, 2, 5, 1, 3, 6

Every thread that was planted is removed, so the tree ends exactly as it started.

Complexity. Time O(n). The predecessor searches look expensive, but count edges: each search walks down the right spine of cur.left. An edge x → x.right belongs to the right spine of the left subtree of at most one node (the nearest ancestor whose left child starts that spine), so across the whole run every edge is walked at most twice by predecessor searches, once when the thread is planted and once when it is removed. Together with the ordinary moves this is O(n). Space O(1): only cur and pred, apart from the output list.

Edge cases and pitfalls