☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Morris Inorder Traversal of a Binary Tree

Hard TUF ID 2792 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Return the inorder traversal of a binary tree (left subtree, then node, then right subtree) as a list of values, using only O(1) extra space apart from the output list. No recursion and no explicit stack. The tree may be changed temporarily but must be restored before the method returns.

Constraints (LeetCode 94): up to 100 nodes, values in [-100, 100]. The space restriction is the real requirement; the Java file also tests a 100000-node tree.

Example 1

        1
       / \
      2   3
     / \   \
    4   5   6
answer = [4, 2, 5, 1, 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: traverse the left subtree, record the node, traverse the right subtree. The call stack keeps track of which node to record once its left subtree is finished.

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). Space O(h) for the call stack, which is O(n) for a skewed tree.

Approach 2: Explicit stack

Intuition. Simulate the recursion. Push nodes while walking as far left as possible; the top of the stack is then the next node in inorder. Pop it, record it, and repeat the process from its right child.

static List<Integer> iterativeStack(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {                                // walk as far left as possible
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    return out;
}

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

Approach 3: Morris traversal

Intuition. The stack exists so that, after finishing the left subtree of cur, we can get back to cur, record it, and continue to the right. Notice which node finishes the left subtree: the rightmost node of cur.left, which is cur’s inorder predecessor pred. Its right pointer is null, so it is free storage.

Morris sets pred.right = cur before descending into the left subtree. This temporary pointer is a thread. When the walk of the left subtree reaches pred and has no real right child to go to, it follows the thread back to cur. Arriving at cur again, the predecessor search finds pred.right == cur, which means “the left subtree is done”: record cur, remove the thread and go right.

Algorithm.

  1. cur = root. While cur != null:
  2. If cur.left == null: record cur, set cur = cur.right.
  3. Otherwise find pred: start at cur.left and move right while pred.right is neither null nor cur.
    • If pred.right == null: set pred.right = cur, then cur = cur.left.
    • Else: 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) {
            out.add(cur.val);
            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, go left
                pred.right = cur;
                cur = cur.left;
            } else {                                         // second arrival via the thread: visit, remove it
                pred.right = null;
                out.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return out;
}

Dry run on Example 1:

cur left child? pred pred.right was action output so far
1 yes 5 null thread 5→1, go left  
2 yes 4 null thread 4→2, go left  
4 no     record 4, follow thread to 2 4
2 yes 4 2 remove thread, record 2, go right 4 2
5 no     record 5, follow thread to 1 4 2 5
1 yes 5 1 remove thread, record 1, go right 4 2 5 1
3 no     record 3, go right 4 2 5 1 3
6 no     record 6, go right (null) 4 2 5 1 3 6

Every thread that was created was also removed, so the tree ends in its original shape.

Complexity. Time O(n). Each predecessor search walks the right spine of one node’s left subtree, and each spine is walked exactly twice: once to create the thread, once to remove it. Those spines are disjoint, so the total work is proportional to the number of edges. Space O(1) beyond the output.

Why Morris inorder is worth knowing

Inorder of a binary search tree is its values in sorted order, so Morris inorder is the standard way to iterate a BST in sorted order with constant memory. That is the basis of O(1)-space solutions to “k-th smallest element in a BST” (stop after k records, but only after cleaning up any threads still in place) and “recover a BST with two swapped nodes” (look for the two places where the sorted order breaks).

Morris preorder is the same code with the record moved from the second arrival to the first.

Edge cases and pitfalls