Morris Traversal, in depth: threading a binary tree for O(1)-space inorder, preorder and postorder walks

Why a tree walk needs memory at all

In an inorder walk, each node is visited after its whole left subtree and before its right subtree. The hard moment is the end of a left subtree. You are standing on its last node, the rightmost one, and you need to get back to the ancestor that is waiting to be visited. A binary tree has no parent pointers, so nothing in the structure leads upward. A stack exists to remember that ancestor.

Look at that rightmost node more closely. It is the ancestor's inorder predecessor, the node visited immediately before it. Because it is the rightmost node of its subtree, its right pointer is always null. So every node with a left child has a predecessor with a free right pointer, and that pointer can point at the node itself. That is the whole idea.

A tree whose null pointers permanently link to inorder neighbours is a threaded binary tree, which needs an extra bit per pointer to tell threads from children. Morris made the threads temporary: each exists only while the walk is inside the subtree it closes, so no extra bit is needed.

The algorithm

Keep one pointer, cur, starting at the root. At each step, exactly one of three cases applies.

1. No left child. There is nothing to do before cur, so visit it and move to cur.right. That pointer is either a real right child or a thread leading up to the successor.
2. A left child, and the predecessor's right pointer is null. This is the first arrival at cur. Set the predecessor's right pointer to cur so the walk can return, then descend into the left subtree.
3. A left child, and the predecessor's right pointer already points at cur. This is the second arrival: the walk came back up through the thread, so the left subtree is finished. Delete the thread, visit cur and move right.

The loop that finds the predecessor walks right from cur.left until the next right pointer is null (first arrival) or is cur itself (second arrival). The second stopping condition is essential. Without it, the search would follow the thread back into cur and loop forever.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right


def morris_inorder(root, visit):
    cur = root
    while cur is not None:
        if cur.left is None:
            visit(cur)
            cur = cur.right              # a real child, or a thread back up
            continue
        pred = cur.left                  # find cur's inorder predecessor
        while pred.right is not None and pred.right is not cur:
            pred = pred.right
        if pred.right is None:           # first arrival: leave a thread back to cur
            pred.right = cur
            cur = cur.left
        else:                            # second arrival: left subtree is finished
            pred.right = None            # restore the tree
            visit(cur)
            cur = cur.right

Worked example: tracing seven nodes

Take the tree in the diagram: 4 at the root, 2 and 6 below it, and leaves 1, 3, 5 and 7. Follow cur step by step.

1. At 4: the left child is 2, and walking right from 2 reaches 3, whose right is null. Set the thread 3 → 4 and move to 2.
2. At 2: the predecessor is 1, whose right is null. Set 1 → 2 and move to 1.
3. At 1: no left child. Visit 1 and follow 1.right, which is the thread, back to 2.
4. At 2 again: the predecessor search reaches 1 and finds 1.right is 2. Clear it, visit 2 and move to 3.
5. At 3: no left child. Visit 3 and follow the thread to 4.
6. At 4 again: the search goes 2 → 3 and finds 3.right is 4. Clear it, visit 4 and move to 6.
7. At 6: set 5 → 6 and move to 5. Visit 5, return to 6, clear the thread, visit 6, move to 7, visit 7. Then cur is null and the walk ends.

The output is 1 through 7. The walk created three threads, one per node with a left child, and deleted all three, so the tree ends exactly as it started.

Why it is still O(n)

The predecessor search looks expensive. Each node with a left child walks down the right spine of its left subtree, and it does so twice: once on first arrival to create the thread, and once on second arrival to find and delete it. A quick bound of O(h) per node would give O(n h) in total, which is O(n²) on a degenerate tree.

The tighter argument counts edges rather than steps. The right spine of cur's left subtree is the chain from cur.left rightwards to the predecessor. Every edge on that chain is a right-child edge, and each right-child edge belongs to the left-subtree spine of exactly one ancestor: the nearest ancestor that reached it by going left. So the spines of all nodes are disjoint, and together they contain at most n - 1 edges. Each spine is walked twice, and cur itself crosses each real edge once and each thread once. That is a constant number of passes over each edge, which gives O(n) time in total.

The constant is real: a Morris walk makes several times as many pointer moves as a stack-based walk and writes to nodes. On a balanced tree, an explicit stack is usually faster. Morris wins when memory is the constraint.

Preorder and reverse inorder: moving one line

Preorder visits a node before its left subtree. In Morris terms, that means visiting on the first arrival instead of the second. Only one line moves:

def morris_preorder(root, visit):
    cur = root
    while cur is not None:
        if cur.left is None:
            visit(cur)
            cur = cur.right
            continue
        pred = cur.left
        while pred.right is not None and pred.right is not cur:
            pred = pred.right
        if pred.right is None:
            visit(cur)                   # the only change: visit on the FIRST arrival
            pred.right = cur
            cur = cur.left
        else:
            pred.right = None
            cur = cur.right

Reverse inorder, descending order in a BST, mirrors the algorithm: swap every left and right, find the successor as the leftmost node of the right subtree, and thread its null left pointer back. Use it for the k largest keys.

Postorder: reversing the right chain

Postorder is the hard case, because a node must be visited after both subtrees, and there is no third arrival at which to do it. The standard solution changes what gets emitted and when. Whenever the walk deletes a thread at cur, it emits the right chain from cur.left down to the predecessor in reverse order. Every node lies on exactly one such chain, so every node is emitted exactly once. A dummy node, with the real root as its left child, makes the root's own right spine one of those chains.

Reversing a chain without memory means reversing its pointers in place, as you would reverse a linked list, walking the reversed chain, and then reversing it back. The reversal leaves the predecessor's right pointer pointing into the chain. The thread deletion that follows sets it back to null.

def _reverse(frm, to):
    """Reverse the right-pointer chain frm -> ... -> to in place."""
    if frm is to:
        return
    x, y = frm, frm.right
    while x is not to:
        z = y.right
        y.right = x
        x, y = y, z


def _visit_chain_backwards(frm, to, visit):
    _reverse(frm, to)
    n = to
    while True:
        visit(n)
        if n is frm:
            break
        n = n.right
    _reverse(to, frm)                    # put the chain back


def morris_postorder(root, visit):
    dummy = Node(None, left=root)        # so the root's own right spine gets emitted
    cur = dummy
    while cur is not None:
        if cur.left is None:
            cur = cur.right
            continue
        pred = cur.left
        while pred.right is not None and pred.right is not cur:
            pred = pred.right
        if pred.right is None:
            pred.right = cur
            cur = cur.left
        else:
            _visit_chain_backwards(cur.left, pred, visit)
            pred.right = None            # also repairs the pointer _reverse left behind
            cur = cur.right

The reversals are the same size as the predecessor walks, so postorder stays O(n) in time and O(1) in space. It is also the most fragile order: an exception in visit between the two reversals leaves a chain pointing backwards.

Applying it: recovering two swapped keys

A classic problem shows where Morris earns its place. Two keys in a BST were swapped by mistake. Restore the tree without changing its structure, using O(1) extra space. Sorted order with two elements swapped contains either one inversion, if the elements were adjacent, or two. The first inversion's larger element and the last inversion's smaller element are the pair to swap back. A recursive inorder walk solves it with O(h) memory. Morris solves it in constant memory.

def recover_swapped(root):
    """Two keys of a BST were swapped by mistake; swap them back in O(1) extra space."""
    prev = first = second = None

    def visit(node):
        nonlocal prev, first, second
        if prev is not None and prev.key > node.key:   # an inversion in sorted order
            if first is None:
                first = prev                           # first inversion: the larger key
            second = node                              # last inversion: the smaller key
        prev = node

    morris_inorder(root, visit)                        # runs to completion: no threads left
    if first is not None:
        first.key, second.key = second.key, first.key

The same pattern, a Morris inorder walk with a prev pointer, also validates a BST and finds the minimum difference between keys in O(1) extra space.

Testing a traversal that mutates

A Morris implementation can produce the right output and still damage the tree, for example by deleting one thread too few. So every test must check two things: the output matches a plain recursive traversal, and the tree's shape is unchanged afterwards.

def shape(n):
    return None if n is None else (n.key, shape(n.left), shape(n.right))

def check(root, morris, reference):
    before = shape(root)
    got, want = [], []
    morris(root, lambda node: got.append(node.key))
    reference(root, want)                    # plain recursive traversal
    assert got == want, (got, want)
    assert shape(root) == before, "threads left behind"

Run check on empty trees, single nodes, one-sided chains and a few thousand random shapes. The code on this page passed exactly that harness for all three orders and the swapped-key recovery.

Failure modes

When to use it, and when not

Reach for Morris when the tree can be very deep and you cannot bound its height, when you work in an environment with a small or fixed stack such as embedded code or a kernel, or when a problem explicitly demands O(1) extra space. If nodes carry parent pointers, use those instead: a parent-pointer walk is also O(1) in space and never writes to the tree. For a self-balancing tree of logarithmic height, an explicit stack of a few dozen entries is simpler, faster and safe to share.

What to do next

1. Implement morris_inorder from memory, then run the check harness on random trees until it passes.
2. Trace the seven-node example on paper for preorder, marking when each thread is created and deleted.
3. Write reverse inorder by mirroring the code, and use it to return the three largest keys, finishing the walk after you have them.
4. Solve the swapped-keys problem both recursively and with Morris, and compare their peak memory on a 100,000-node chain.
5. Read Kth smallest in a BST for the early-exit trap, then Populate next right pointers for another O(1)-space technique that reuses the tree's own pointers.
6. Compare the pointer tricks in Floyd's cycle detection: both trade memory for extra passes over a linked structure.