Morris Traversal: The Tree Rewires Itself So You Don't Need a Stack

Your binary tree needs a stack. Or recursion. Either way you're paying O(h) memory for the privilege. Morris traversal skips the invoice entirely. It traverses an entire tree inorder, preorder, or postorder using O(1) auxiliary space by temporarily borrowing null pointers already sitting idle in the tree, using them as threads back up, then erasing every trace when done.

The mental model: before descending into a left subtree, find the inorder predecessor (the rightmost node of that subtree), point its null right pointer back at the current node as a thread, then descend. When you arrive at that predecessor node again later, follow the thread back up, remove it, and continue right. The tree guides you home without a stack.

Joseph Morris published this in 1979 in "Traversing Binary Trees Simply and Cheaply" (Information Processing Letters, 9(5): 197-200). It answered a challenge Knuth posed in 1968: can you traverse a tree inorder without a stack, without recursion, without tagging nodes, and leave the tree completely unmodified when done? Knuth wasn't sure it was possible. Morris showed it was, and the mechanism turned out to be embarrassingly simple.

Both Approaches Pay the Same Tax

When you do recursive inorder traversal, the call stack at any moment holds the path from the root to the current node. That path is h frames long. For a balanced tree, h = O(log n). For a degenerate (fully right-skewed) tree, h = O(n). In either case, O(h) memory scales with the tree.

The iterative approach with an explicit stack is no different. You push nodes to remember where to return after finishing a left subtree. You're just moving the call stack to the heap. Moving a problem somewhere else doesn't make it go away. Ask any memory leak.

The fundamental problem both approaches share: when you go left, you need a way to return to the parent. Morris traversal solves that by creating the return path in the tree itself, rather than in a separate structure.

Half Your Pointers Point at Nothing

Here's a fact that should bother you.

In any binary tree with n nodes, there are exactly n+1 null pointers. The Perlis-Thornton observation from 1960 is that these nulls are wasted. More than half of all pointers in a tree point nowhere. They're just sitting there, completely inert, doing nothing. Threading replaces them with pointers to inorder predecessors or successors, enabling traversal without a stack.

Morris traversal does this temporarily. It creates threads on demand, uses them, then erases them, so the tree is fully unmodified when done.

For any node N with a left child, its inorder predecessor is the rightmost node of N's left subtree. That node always has a null right pointer in the unmodified tree (because it is the rightmost node; nothing is to its right). Morris traversal sets that null pointer to N, creating a thread that leads back up.

Before and after: node 3's null right pointer becomes a thread pointing back to node 4. The yellow dashed arrow is the thread; the original edge structure is unchanged.

The thread looks like any other right pointer. The trick is distinguishing it from an original edge: when the predecessor-finding loop reaches a node whose right pointer points back to the current node being processed, that right pointer is a thread.

Each node is processed twice:

1. First encounter. Current node has a left child. Find the inorder predecessor. Its right pointer is null. Set it to current. Descend left.
2. Second encounter. Current node has a left child again. Find the inorder predecessor. Its right pointer is current (the thread we set). Remove the thread. For inorder: visit the current node now. Move right.

Nodes with no left child are visited once: visit immediately, move right.

Left: first encounter, thread gets set, algorithm descends left. Right: second encounter, thread gets removed and the node is visited. The entire algorithm is this two-state check.

The "0 vs null" distinction matters here. Zero is a value. Null is the absence of a pointer. Morris traversal only borrows null right pointers because it can detect them reliably. If a right pointer has a value, it points somewhere real. If it's null, it's free real estate.

"0 sheets remaining" still points to something. NULL means the roll isn't there at all. Morris traversal only borrows the rolls that aren't there yet.

Step-by-Step: Tracing Morris Inorder

Here's the full trace on a five-node tree. Don't skip it. The algorithm looks confusing until you watch it run once. Expected output: 1, 2, 3, 4, 5.

Initial tree:

        4
       / \
      2   5
     / \
    1   3

Step 1, current = 4
  Has left child (2). Find predecessor: start at 2, follow right to 3.
  3.right is null → set thread: 3.right = 4. Move to 4.left = 2.

        4 ◄─────────────────┐  (thread)
       / \                  │
      2   5                 │
     / \                    │
    1   3 ──────────────────┘

Step 2, current = 2
  Has left child (1). Find predecessor: start at 1.
  1.right is null → set thread: 1.right = 2. Move to 2.left = 1.

        4 ◄─────────────────┐
       / \                  │
      2 ◄──┐  5             │
     / \   │                │
    1   3 ─┘                │
    └───────────────────────┘
    (1.right = 2, 3.right = 4)

Step 3, current = 1
  No left child. Visit 1. Move to 1.right = 2 (via thread).
  Output: [1]

Step 4, current = 2
  Has left child (1). Find predecessor: start at 1. 1.right = 2 = current.
  Thread found → remove: 1.right = null. Visit 2. Move to 2.right = 3.
  Output: [1, 2]

Step 5, current = 3
  No left child. Visit 3. Move to 3.right = 4 (via thread).
  Output: [1, 2, 3]

Step 6, current = 4
  Has left child (2). Find predecessor: start at 2, follow 2.right = 3.
  3.right = 4 = current. Thread found → remove: 3.right = null. Visit 4.
  Move to 4.right = 5.
  Output: [1, 2, 3, 4]

Step 7, current = 5
  No left child. Visit 5. Move to 5.right = null. Done.
  Output: [1, 2, 3, 4, 5] ✓

The tree is fully restored. Every thread created was removed.

At step 2, both threads exist at once: 1.right = 2 and 3.right = 4. Current is at node 1. From here, the algorithm unwinds back up the tree via these threads.

How Fast, How Much Memory

Why O(n) Time

The inner while loop looks expensive. If the tree is a right chain hanging off a single root with a left child, that loop traverses n-1 nodes just for the root. That looks like O(n²). Go ahead, panic. I'll wait.

It's not O(n²). Here is the proof.

Claim: every original right edge (u, v) in the tree is traversed in the predecessor-finding inner loop at most twice, across the entire traversal.

Consider any right edge (u, v) where v = u.right in the original tree. For this edge to appear in the inner loop, u must be on the right spine of some node N's left subtree. The right spine of N.left is a path that follows only right pointers starting from N.left. Since N.left is the left child of N, reaching u via only right pointers from N.left means u must be at the end of a rightward chain starting at N.left.

The right spine of an ancestor A.left and the right spine of any descendant N.left are disjoint. Following right pointers from A.left can only visit right children. N.left is a left child, so no right-pointer path from A.left can enter N.left's subtree. Each right edge therefore belongs to the right spine of exactly one node's left subtree.

So the inner loop traverses edge (u, v) exactly twice: once when setting the thread for N, once when removing it. With n-1 edges total, the cumulative inner-loop work is 2(n-1) = O(n). Add the O(n) cost of stepping through each node, and the algorithm is O(n) overall.

Why O(1) Space

There is no stack, no recursion, and no auxiliary data structure. The threads live in right pointers the caller already owns. The algorithm uses exactly three local pointer variables: current, predecessor, and a loop counter. O(1) regardless of n or tree shape.

One Threading Idea, Three Traversal Orders

Same tree, same threading mechanism, different visit timing. Circled numbers show the order nodes are visited. Inorder visits on thread removal; preorder visits on thread creation.

Inorder (Left-Root-Right)

Visit the node on the second encounter, when you find and remove the thread. For nodes with no left child, visit immediately then move right. This is the form traced above.

Preorder (Root-Left-Right)

One change from inorder: visit the node on the first encounter (when setting the thread), not the second. For nodes with no left child, visit immediately then move right. The thread-setting logic is identical.

if predecessor.right is None:
    visit(current)          # moved here from the else branch
    predecessor.right = current
    current = current.left
else:
    predecessor.right = None
    # do NOT visit here
    current = current.right

Postorder (Left-Right-Root)

The cleanest O(1) space approach uses a mirror: traverse in Root-Right-Left order (mirrored preorder), collect the output, then reverse it. Reversed Root-Right-Left is Left-Right-Root, which is postorder.

Implementing Root-Right-Left requires the same threading logic as inorder, but mirrored: thread left-spine nodes back to their right-ancestor, with the predecessor as the leftmost node of the right subtree.

The output list holding the collected results uses O(n) space, but that is the output itself, not auxiliary working space. The auxiliary space of the algorithm remains O(1).

One Structure, Every Language

from __future__ import annotations

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

def morris_inorder(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current        # set thread
                current = current.left
            else:
                predecessor.right = None           # remove thread
                result.append(current.val)
                current = current.right
    return result

def morris_preorder(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right
            if predecessor.right is None:
                result.append(current.val)         # visit before descending
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result

The Problems Morris Traversal Is Made For

Morris traversal is the right tool when you need to traverse a binary tree and an O(h) space budget is either unavailable or unacceptable.

The common scenarios:

• BST inorder operations under strict memory constraints. Embedded systems or real-time environments where the call stack is a fixed, small resource. Any BST operation that needs a sorted view of the elements (range queries, validation, conversion to sorted array) can use Morris traversal instead of a recursive walk.
• Finding the kth smallest or largest element in a BST. Inorder traversal of a BST gives sorted order. With Morris traversal you count through that sorted order using O(1) space, stopping when you reach element k.
• Validating a BST. Inorder traversal should produce strictly increasing values. Morris traversal checks this in O(n) time and O(1) space by tracking the previously visited value.
• Converting a BST to a sorted doubly linked list in-place. The threading mechanism is structurally similar to what you'd do to build the list anyway.
• Recovering a BST with two swapped nodes. You find the two nodes where the inorder sequence is out of order, then swap their values. Morris traversal does this in O(1) auxiliary space.
• Flattening a binary tree to a linked list. Preorder Morris traversal visits nodes in exactly the order the flattened list needs them, without an explicit stack.

When to Reach for Morris

The signal: tree traversal problem plus a hard O(1) space constraint, or the follow-up "can you do it without a stack?"

That follow-up is common in interviews. The stack-based iterative version is well known. Morris traversal is the answer when the interviewer pushes for constant space. If the interviewer asks it once, they're probing. If they ask twice, they want you to know this specifically.

Other signals:

• BST property used during traversal (inorder gives sorted order, and you need to do something with consecutive values).
• Problem explicitly says the tree can be modified during traversal and then restored.
• The constraint block mentions "O(1) extra memory" or "do not use recursion."

Example 1: Kth Smallest Element in BST (LeetCode 230)

Problem. Given the root of a BST and an integer k, return the kth smallest value among all nodes (1-indexed).

Why Morris fits. Inorder traversal of a BST visits nodes in ascending order. You need to stop at position k. The natural approach is recursive inorder, which is O(h) space. The follow-up in the problem explicitly asks for O(1) space solutions.

With Morris inorder traversal, you maintain a counter. Each time you visit a node (the "remove thread and visit" step), you increment the counter. When the counter reaches k, return the current value and bail out early. Since you exit early, you also need to clean up any threads you set but didn't get a chance to remove. The simplest approach: just stop modifying the tree once you find your answer, and run the algorithm to completion without collecting output, which will still remove all threads.

def kth_smallest(root: TreeNode, k: int) -> int:
    count = 0
    current = root
    while current:
        if current.left is None:
            count += 1
            if count == k:
                return current.val
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                count += 1
                if count == k:
                    return current.val
                current = current.right
    return -1  # unreachable for valid k

Time O(n) worst case, O(k + h) average (the thread-removal cleanup for nodes after position k adds at most one pass back up the left spine). Space O(1).

Example 2: Recover Binary Search Tree (LeetCode 99)

Problem. Two nodes in a BST were swapped by mistake. Recover the tree by swapping them back. You must do it in O(n) time.

Follow-up: can you do it in O(1) space?

Why Morris fits. Inorder traversal of a correct BST produces strictly increasing values. With two nodes swapped, exactly one or two "inversions" appear: places where the current value is smaller than the previous value. The first inversion: the first node is the candidate. The second inversion: the second node is the candidate. If there is only one inversion, the two adjacent nodes are swapped.

You need to track prev (the previously visited node) and watch for inversions. Morris inorder is a drop-in replacement for the recursive traversal.

def recover_tree(root: TreeNode | None) -> None:
    first = second = prev = None
    current = root
    while current:
        if current.left is None:
            if prev and prev.val > current.val:
                if first is None:
                    first = prev
                second = current
            prev = current
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                if prev and prev.val > current.val:
                    if first is None:
                        first = prev
                    second = current
                prev = current
                current = current.right
    if first and second:
        first.val, second.val = second.val, first.val

The only extra variables are first, second, and prev: three pointers, O(1) space. The Morris threading does all the traversal work.

The Short Version

• Morris traversal achieves O(1) auxiliary space by temporarily threading the tree: the inorder predecessor's null right pointer becomes a pointer back to the current node.
• Each node is processed twice: once to set the thread and descend left, once to remove the thread and visit (for inorder).
• Total time is O(n) because each original right edge is traversed at most twice, one pass per direction.
• The three variants differ in which visit triggers the output: inorder visits on thread removal, preorder visits on thread creation.
• Postorder uses the mirrored preorder trick: traverse root-right-left, collect to a list, reverse.
• The tree is fully restored at the end of the traversal.
• The signal for reaching for this technique is any BST traversal problem with an O(1) space constraint, or the interview follow-up "now do it without a stack."

If you want to practice explaining Morris traversal out loud under interview conditions, SpaceComplexity runs voice-based DSA mock interviews where you reason through exactly this kind of follow-up in real time, with rubric-based feedback on both your explanation and your code.

For binary tree traversal using an explicit stack, see the iterative inorder traversal reference. For the O(h) space cost that Morris replaces, Recursion Space Complexity walks through why the call stack is bounded by the depth of the deepest active frame. For BST properties that Morris inorder relies on, The Binary Search Tree covers the core invariant and all standard operations.

Further Reading

• Threaded binary tree (Wikipedia), the theoretical foundation Morris traversal builds on, including the Perlis-Thornton history
• Morris traversal for Inorder (GeeksforGeeks), step-by-step walkthrough with diagrams
• Morris traversal for Preorder (GeeksforGeeks), the single-line change from inorder to preorder, spelled out
• Morris traversal for Postorder (GeeksforGeeks), the mirrored preorder approach in detail
• Binary Tree Inorder Traversal (LeetCode 94), the canonical problem where Morris traversal is one of three expected solutions
• Kth Smallest Element in a BST (LeetCode 230), the standard interview vehicle for the O(1) space follow-up