Morris Traversal and O(1)-Space Tree Walks

You write the recursive in-order traversal, it is accepted, and then: “can you do it without recursion?” You write the explicit stack. “Can you do it in O(1) space?” — and this is where most candidates stop, because with no stack and no recursion there is nothing left to remember where to return to.

Morris traversal’s answer is to store the return path in the tree itself. The rightmost node of a left subtree has a null right pointer doing nothing; borrow it to point back up at the ancestor. The walk falls off the bottom of the subtree, lands on that pointer, and arrives exactly where a return would have taken it. Undo the pointer on the way past and the tree is unchanged at the end.

This is worth knowing for two reasons, and only one of them is the technique. The other is that “O(1) space” in tree questions is a precise claim about what counts — and being able to say why recursion is O(h), why the stack version is also O(h), and where Morris’s O(1) is actually paid for, is the part of the answer that scores.

What you’ll learn

• The thread — what it is, when it is created, when it is removed, and why each node with a left child is visited exactly twice.
• Why the traversal is still $O(n)$ even though it walks down the right spine of every left subtree.
• The honest cost: the tree is temporarily mutated, which rules the technique out in concurrent or read-only settings.
• The variants: Morris pre-order (a two-line change), and why Morris post-order is much worse than the other two.
• The three follow-up questions this pattern is really asked as: LC 94, LC 99 and LC 114.

The cue

You are looking at a Morris traversal when…

• The problem statement or the interviewer says “O(1) extra space” about a tree walk, or asks for a “constant space” follow-up to a traversal you already wrote.
• LeetCode’s problem page has the note “could you solve it in O(1) space?” — LC 94 and LC 99 both do, and that sentence is the entire reason those problems are more than warm-ups.
• You need one in-order pass over a BST and cannot afford $O(h)$, e.g. a very deep degenerate tree where the recursion would blow Python’s 1000-frame limit.

The reframe: a traversal needs to know where to go back to. Recursion stores that in the call stack; the explicit version stores it in a list; Morris stores it in a pointer that was null anyway. The information does not disappear — it moves into unused space in the data structure.

Reach for something else when the tree may be shared or read concurrently (the transient mutation makes Morris unsafe), when the tree is immutable, or when $O(h)$ is fine — which is almost always. Say the plain recursion first, then offer this.

Visual intuition

Watch the thread edges appear and disappear. Every node with a left child is arrived at twice: the first time installs the thread, the second consumes it and emits the value.

treeMorris in-order on a balanced BST: threads stand in for the call stackLC 94 · O(n) time, O(1) space

1def morris_inorder(root):2    out, cur = [], root3    while cur:4        if cur.left is None:5            out.append(cur.val)       # visit6            cur = cur.right           # a real edge, or a thread back up7        else:8            pred = cur.left9            while pred.right and pred.right is not cur:10                pred = pred.right     # rightmost node of the left subtree11            if pred.right is None:12                pred.right = cur      # thread: remember where to return13                cur = cur.left14            else:15                pred.right = None     # undo the thread — restore the tree16                out.append(cur.val)   # visit, on the SECOND arrival17                cur = cur.right18    return out

cur4threads0visited0

startIn-order without recursion and without a stack. The trick: before descending into a left subtree, hang a temporary **thread** from that subtree's rightmost node back up to the current node. When the walk falls off the bottom right of the subtree it lands on the thread and arrives back at the ancestor — which is exactly what popping the call stack would have done, at O(1) extra space instead of O(h).

Play‹›1/12⟲

Count the thread edges across the whole trace: each one is created once and removed once, so the tree ends identical to how it started. The 'threads' watch is never above the number of ancestors currently pending -- that is the stack, expressed in pointers the tree was not using.

And on a left-degenerate tree, where the recursive version would use $O(n)$ stack frames and Python would raise RecursionError:

treeA left-leaning chain: recursion needs n frames, Morris needs two variablesthe case that motivates it

1def morris_inorder(root):2    out, cur = [], root3    while cur:4        if cur.left is None:5            out.append(cur.val)       # visit6            cur = cur.right           # a real edge, or a thread back up7        else:8            pred = cur.left9            while pred.right and pred.right is not cur:10                pred = pred.right     # rightmost node of the left subtree11            if pred.right is None:12                pred.right = cur      # thread: remember where to return13                cur = cur.left14            else:15                pred.right = None     # undo the thread — restore the tree16                out.append(cur.val)   # visit, on the SECOND arrival17                cur = cur.right18    return out

cur5threads0visited0

startIn-order without recursion and without a stack. The trick: before descending into a left subtree, hang a temporary **thread** from that subtree's rightmost node back up to the current node. When the walk falls off the bottom right of the subtree it lands on the thread and arrives back at the ancestor — which is exactly what popping the call stack would have done, at O(1) extra space instead of O(h).

Play‹›1/8⟲

Each node threads to its parent on the way down, and the chain unwinds one thread at a time on the way back. This is the shape where Morris is not a party trick: at n = 10^5 the recursive solution raises RecursionError and the stack solution allocates a list of 10^5 nodes.

The template

morris.py

def morris_inorder(root):
    """In-order traversal in O(n) time and O(1) extra space."""
    out, cur = [], root
    while cur:
        if cur.left is None:
            out.append(cur.val)              # visit: nothing is to the left
            cur = cur.right                  # a real edge, or a thread back up
        else:
            pred = cur.left                  # in-order predecessor of cur ...
            while pred.right and pred.right is not cur:
                pred = pred.right            # ... = rightmost node of left subtree
            if pred.right is None:
                pred.right = cur             # FIRST arrival: install the thread
                cur = cur.left
            else:
                pred.right = None            # SECOND arrival: undo the thread
                out.append(cur.val)          # ... and only now visit cur
                cur = cur.right
    return out
 
 
def morris_preorder(root):
    """Pre-order: identical, except the visit moves to the FIRST arrival."""
    out, cur = [], root
    while cur:
        if cur.left is None:
            out.append(cur.val)
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if pred.right is None:
                out.append(cur.val)          # <-- the only change: visit here
                pred.right = cur
                cur = cur.left
            else:
                pred.right = None
                cur = cur.right
    return out

Three lines carry the whole idea:

• while pred.right and pred.right is not cur — the is not cur half is what makes the second arrival detectable. Without it the loop follows its own thread in a circle and hangs. This is the single most common Morris bug.
• pred.right = cur installs the return path. It is a write to the tree, and the reason this technique is unsafe to run on a structure anyone else can see.
• pred.right = None restores it. If the traversal exits early — a return the moment you find the answer — some threads are still installed and the tree is left corrupted. That matters for LC 230, and it is the trap in that problem’s Morris solution.

Dry run

Tree [4, 2, 6, 1, 3, 5, 7] — the one in the visualization above:

text

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

step	cur	left child?	action	threads live	output
1	4	yes	pred = 3 (rightmost of left subtree); thread 3→4; go left	3→4	—
2	2	yes	pred = 1; thread 1→2; go left	3→4, 1→2	—
3	1	no	visit 1; right is the thread → climb to 2	3→4	1
4	2	yes	pred = 1, and 1.right is cur → second arrival: cut thread, visit 2, go right to 3	3→4	1 2
5	3	no	visit 3; right is the thread → climb to 4	—	1 2 3
6	4	yes	second arrival: cut thread, visit 4, go right to 6	—	1 2 3 4
7	6	yes	pred = 5; thread 5→6; go left	5→6	1 2 3 4
8	5	no	visit 5; climb the thread to 6	—	1 2 3 4 5
9	6	yes	second arrival: cut thread, visit 6, go right to 7	—	… 6
10	7	no	visit 7; right is null → cur = None, loop ends	—	1 2 3 4 5 6 7

Three things this makes concrete that the code does not:

• Threads live at most h at a time, and always exactly the pending ancestors. At step 2 the live threads are 3→4 and 1→2 — the two nodes whose values have not been emitted yet and whose left subtrees are still being walked. That set is the recursion stack, stored in pointers that were null.
• Every value is emitted exactly once, but nodes with a left child are arrived at twice. 4 and 2 and 6 each appear twice in the cur column. Counting arrivals is how you convince someone the algorithm is $O(n)$ and not $O(n \log n)$: the extra work is one downward walk per thread, each edge is traversed a bounded number of times, and $2n$ arrivals is still $O(n)$.
• The tree is fully restored by step 10. The threads column ends empty. Say that out loud when asked “does it modify the tree?” — the answer is “yes, transiently, and it is provably restored if the walk runs to completion”.

Complexity

Traversal	Time	Extra space	Notes
Recursive in-order	$O(n)$	$O(h)$	$O(n)$ on a degenerate tree; RecursionError past ~1000 in CPython
Explicit stack	$O(n)$	$O(h)$	same bound, no recursion limit
Morris in-order	$O(n)$	$O(1)$	two pointers; mutates transiently
Morris pre-order	$O(n)$	$O(1)$	one line moved
Morris post-order	$O(n)$	$O(1)$	needs a reversed sub-list walk; rarely worth it

The $O(n)$ time claim deserves the argument, because the nested while looks suspicious. Each edge of the tree is walked at most a constant number of times: once descending, once during the predecessor search that installs a thread, and once when that thread is followed back up. Summed over all edges that is $\le 3(n-1)$ pointer moves — the same reasoning as for a monotonic stack, where a nested loop is also amortised.

What “O(1) space” does and does not mean

The output list does not count — it is the answer, not scratch space. That is why LC 94’s “O(1) space” follow-up is coherent at all. What does count is anything whose size grows with the tree: a stack, a visited set, a parent map, or the recursion frames. Recursion’s $O(h)$ is invisible in the source, which is exactly why interviewers like the question.

The variant map

Problem / variant	Where the visit happens	The one thing that changes
LC 94 In-order traversal	second arrival	the base template
Morris pre-order	first arrival	move out.append above pred.right = cur
Morris post-order	—	reverse-thread on right children and reverse the output, or emit the reversed right spine per thread; four times the code for the same bound
LC 99 Recover BST	second arrival	compare each visited value with the previous one; the two out-of-order pairs identify the swapped nodes
LC 230 Kth smallest in BST	second arrival	count visits and stop at k — but you must finish undoing the threads first, or the tree is left corrupted
LC 114 Flatten to linked list	first arrival	the same threading idea applied directly: for each node, thread its predecessor’s right to its right subtree, then move the left subtree to the right
LC 897 Increasing order search tree	second arrival	rewire as you visit instead of appending
Sum / min / max in one pass	either	replace the output list with an accumulator, and the space claim becomes unambiguous

Morris pre-order is worth a moment: it is the same traversal, and only the line where the value is emitted differs. If you can explain why moving one line converts in-order into pre-order, you have understood the two-arrivals structure — and that is a better answer than reciting the code.

Pitfalls

• Omitting and pred.right is not cur. The predecessor search then follows the thread it installed earlier and loops forever. Symptom: a hang, not a wrong answer.
• Forgetting pred.right = None. The traversal still produces the right values the first time, and leaves a tree with cycles. Any later use of that tree hangs or recurses forever, so the failure appears far from the cause.
• Returning early with threads installed (LC 230 with a k cutoff). The values are correct and the tree is corrupt. Either finish the walk and discard the rest, or restore the outstanding threads before returning.
• Claiming O(1) while building a list of every node. If the problem asks for the traversal as a list, the output is $O(n)$ and the extra space is $O(1)$. State which you mean; conflating them makes the claim sound wrong.
• Using it on a tree someone else can read. Between the install and the undo, the tree has cycles. In production code that is a data race, and in an interview saying so unprompted is worth more than the algorithm.
• Reaching for Morris first. The recursive version is three lines and correct. Write it, name its $O(h)$ space, then offer Morris as the constant-space answer. Leading with Morris reads as memorisation.
• Mixing up predecessor and successor. The thread hangs from the rightmost node of the left subtree (the in-order predecessor) to cur. Threading from the leftmost node of the right subtree is a different, broken algorithm.

Interview follow-ups

They ask	What they’re checking	The answer
“Do it in O(1) space”	Whether you know this exists	Morris: thread the in-order predecessor’s null right pointer back to the current node, so the walk returns without a stack. $O(n)$ time, two pointers of extra space
“Why is it O(n) and not O(n log n)?”	Amortised reasoning	Each edge is traversed a bounded number of times — down, during one predecessor search, and back up along one thread — so at most about $3n$ pointer moves in total
“Does it modify the tree?”	Honesty and precision	Yes, transiently. Every thread installed is removed on the second arrival, so a completed traversal leaves the tree identical. An early exit does not, and concurrent readers would observe cycles
“Make it pre-order”	Whether you understand the structure	Move the visit from the second arrival to the first — one line. In-order emits when the left subtree is finished; pre-order emits before descending
“What about post-order?”	Judgement	Possible — mirror the algorithm on left children and reverse the output — but it is four times the code for the same asymptotics. In an interview I would say that and then write the stack version
“Where does Morris actually beat the stack version?”	Whether you can justify the trade	Only when $O(h)$ is genuinely unaffordable: a degenerate tree of $10^5$ nodes, or an embedded/memory-bounded setting. Otherwise the stack version is clearer and safe under sharing
“Use it for LC 230, stopping at k”	The early-exit trap	Count on each visit, but do not return the instant the count hits k — first undo the outstanding threads, otherwise you hand back a tree containing cycles
“Could you find the two swapped nodes in a BST in O(1) space?” (LC 99)	Composition	Yes — Morris in-order, comparing each value to the previous. The first descent gives the larger node, the second the smaller; with only one descent the pair is adjacent

Practice

6 problems

2 easy3 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○94Binary Tree Inorder Traversaleasy
• ○897Increasing Order Search Treeeasy
• ○114Flatten Binary Tree to Linked ListmediumLeetCode Top Interview 150
• ○173Binary Search Tree IteratormediumLeetCode Top Interview 150
• ○230Kth Smallest Element in a BSTmediumNeetCode 150Blind 75LeetCode Top Interview 150
• ○99Recover Binary Search Treehard

Exercises

LC 94 — Binary Tree Inorder Traversal, in O(1) space · Easy

pch.exerciseTag pch.exerciseTitle

LC 99 — Recover Binary Search Tree, in O(1) space · Hard

pch.exerciseTag pch.exerciseTitle

LC 114 — Flatten Binary Tree to Linked List, in O(1) space · Medium

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag Morris traversal — self-check

1. What exactly is a Morris 'thread'?

   A A pointer from a node to its parent, added to every node B A temporary right pointer from the rightmost node of a left subtree back up to that subtree's root's ancestor — replacing the stack entry that would have said where to return C A thread of execution walking the right subtree in parallel D A copy of the tree with parent links
   pch.quizShowAnswer

   B — A temporary right pointer from the rightmost node of a left subtree back up to that subtree's root's ancestor — replacing the stack entry that would have said where to return — It reuses a pointer that was null. That is why the space is O(1): the return information moves into space the data structure was not using.

2. Why does the predecessor search need the condition `pred.right is not cur`?

   A For speed B Because without it the search follows the thread it installed earlier and loops forever — it is also the test that distinguishes a first arrival from a second C To handle empty trees D To avoid visiting a node twice
   pch.quizShowAnswer

   B — Because without it the search follows the thread it installed earlier and loops forever — it is also the test that distinguishes a first arrival from a second — The symptom of dropping it is a hang, not a wrong answer, which makes it hard to spot by testing on small inputs. The condition does double duty: loop guard and arrival counter.

3. Does Morris traversal modify the tree?

   A No, never B Yes, transiently — each thread is removed on the second arrival, so a completed traversal leaves the tree identical, but mid-walk it contains cycles C Yes, permanently D Only for BSTs
   pch.quizShowAnswer

   B — Yes, transiently — each thread is removed on the second arrival, so a completed traversal leaves the tree identical, but mid-walk it contains cycles — The precise version of this answer is what an interviewer is after: restored if the walk completes, corrupt if you exit early, and unsafe for concurrent readers either way.

4. You adapt Morris to LC 230 and return as soon as the visit count reaches k. What is wrong?

   A Nothing B Threads installed for ancestors you never returned to are still in the tree, so you hand back a structure containing cycles C The count will be off by one D It becomes O(n log n)
   pch.quizShowAnswer

   B — Threads installed for ancestors you never returned to are still in the tree, so you hand back a structure containing cycles — The values returned are correct, which is what makes this dangerous. Either walk to completion and discard the rest, or explicitly undo the outstanding threads before returning.

5. How do you turn Morris in-order into Morris pre-order?

   A Reverse the output B Move the visit from the second arrival to the first — emit the value just before installing the thread and descending left C Swap left and right everywhere D It is not possible in O(1) space
   pch.quizShowAnswer

   B — Move the visit from the second arrival to the first — emit the value just before installing the thread and descending left — One line moves. Being able to say why is a better demonstration of understanding than reproducing the in-order code: in-order emits once the left subtree is done, pre-order emits before descending into it.

6. Why is the nested `while` still O(n) overall?

   A Because the tree is balanced B Because each edge is traversed a bounded number of times — descending, during one predecessor search, and once following the thread back up — for about 3n pointer moves total C Because the inner loop runs at most log n times D It is not; Morris is O(n log n)
   pch.quizShowAnswer

   B — Because each edge is traversed a bounded number of times — descending, during one predecessor search, and once following the thread back up — for about 3n pointer moves total — Same amortised argument as the monotonic stack: count total work per edge rather than worst-case work per iteration. On a balanced tree the inner loop is short; on a degenerate one it is long but happens rarely.

Recall card

• Cue — “O(1) extra space” asked of a tree traversal, or a follow-up to the stack version.
• Idea — store the return path in the tree: thread the in-order predecessor’s null right pointer up to the current node.
• Loop — no left child → visit, go right. Left child → find rightmost of the left subtree; if its right is null, thread it and descend left; if it is cur, cut the thread, visit, go right.
• Two arrivals — every node with a left child is reached twice: install, then consume. In-order visits on the second, pre-order on the first.
• Cost — $O(n)$ time (each edge walked a constant number of times), $O(1)$ extra space.
• Caveats — the tree has cycles mid-walk; an early exit leaves it corrupt; unsafe with concurrent readers.
• Ladder — LC 94 (the base), LC 99 (compare with the previous value), LC 114 (the same rewiring, made permanent).

Recap

• Morris traversal removes the $O(h)$ stack by putting the return path into pointers the tree was not using. That is the only idea; everything else is the bookkeeping that installs and removes them.
• The structure to hold in your head is two arrivals per node with a left child — which also explains pre-order (visit on the first) and the $O(n)$ bound (bounded work per edge).
• The honest cost is transient mutation. Say it before you are asked; it is the difference between reciting an algorithm and understanding a trade-off.
• Do not lead with it. Recursion, then the stack, then “and if you want $O(1)$ space…” — that ordering is what the follow-up is testing.

Next: Binary Lifting and Sparse LCA — the other way to answer ancestor questions, when a single tree serves millions of queries.