cf.completefrontend
TREES & TRIES · ADVANCED

Morris traversal

Walk a binary tree in order using no stack at all, by adding temporary links back up the tree and removing them afterwards.

Time O(n)Space O(1)3 practice problemsStep-through picture

The idea

A normal inorder walk needs a stack, either the call stack or your own, to remember how to get back up to a parent. That memory grows with the tree's height. Morris traversal needs only a few variables, whatever the tree's size.

The idea: before going into a node's left subtree, find the node that will be visited just before it. That node is called its predecessor. It is the rightmost node of the left subtree, and its right pointer is always null. Point that empty right at the current node. This temporary link is called a thread. Later, when the walk reaches the predecessor and follows its right pointer, it lands back on the current node, with no stack needed.

When the walk comes back through a thread, it removes the thread, so the tree ends exactly as it started.

An everyday example

Leaving a rope to climb back out

You climb down into the left side of a canyon. Before you go, you walk to the far bottom-right point of that side and tie a rope from there back up to where you stand now. Then you explore the left side freely. When you reach that bottom-right point, the rope takes you straight back up. You untie the rope on your way, so the canyon looks untouched.

How the example maps to the code
In the exampleIn the code
Where you stand nowcurrent
The bottom-right point of the left sidepred, the rightmost node of current.left
Tying the ropepred.right = current
Climbing back up by the ropecurrent = current.right landing on a thread
Untying the ropepred.right = null

From the slow way to morris traversal

  1. Both the recursive walk and the stack walk spend O(h) memory for one reason: after finishing a left subtree, they need a way back up to the parent. Tree pointers only go down, so the way back has to be stored somewhere.
  2. But the tree already has many unused pointers. A tree with n nodes has n + 1 empty child slots, null values that point nowhere. If some of them could point back up at just the right moment, we wouldn't need a stack at all.
  3. Which slot? In inorder, the node visited just before current is the rightmost node of its left subtree, called its predecessor. Being rightmost, its right is always null. And the walk's tour of that left subtree ends at exactly that node. So if pred.right points at current, the walk's next "go right" from pred lands exactly on current.
  4. So before going left, find pred and set pred.right = current, a temporary link called a thread. When the walk later reaches current again and finds pred.right === current, the left side must be done: remove the thread, record current, and go right. That loop of tie, go down, come back, untie is Morris traversal.

How it works

  1. Start with current = root.
  2. If current has no left child, record current.val and move to current.right.
  3. Otherwise find pred: start at current.left and keep going right while pred.right is not null and not current.
  4. If pred.right is null, this is the first visit: set the thread pred.right = current and move left.
  5. If pred.right is current, the left subtree is done: remove the thread, record current.val, and move right.
  6. Stop when current is null.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function morrisInorder(root) {
  2. const result = [];
  3. let current = root;
  4. while (current !== null) {
  5. if (current.left === null) {
  6. result.push(current.val);
  7. current = current.right;
  8. } else {
  9. let pred = current.left;
  10. while (pred.right !== null && pred.right !== current) {
  11. pred = pred.right;
  12. }
  13. if (pred.right === null) {
  14. pred.right = current;
  15. current = current.left;
  16. } else {
  17. pred.right = null;
  18. result.push(current.val);
  19. current = current.right;
  20. }
  21. }
  22. }
  23. return result;
  24. }

How fast it is

TimeO(n)
Extra memoryO(1)

Each edge is walked a fixed number of times while threads are set and removed. Only current and pred are stored, whatever the tree's size, not counting the output list.

  • Best caseO(n)

    A chain leaning right, where no node has a left child. No threads are made, and each node is visited once.

  • Average caseO(n)

    A random tree: about half the nodes have a left child, and each of those costs one extra visit plus a short predecessor walk.

  • Worst caseO(n)

    A tree whose left subtrees have long right edges, like a left child with a right chain of 1,000 nodes. That chain is walked twice, but every edge is still walked a fixed number of times, so the total stays O(n), with a larger constant than the stack walk.

Common mistakes

  • Writing the predecessor loop as while (pred.right !== null) only. On the second visit it follows the thread back to current and walks in a circle forever.
  • Forgetting pred.right = null. The answer can still look right, but the tree is left changed and full of loops.
  • Returning early from inside the loop. Threads stay in the tree. Record what you need and let the walk finish.
  • Using it on a tree that other code reads at the same time. The temporary threads are visible to that code.

When to use it

Look for these clues in a problem:

  • The problem asks for an inorder walk with O(1) extra memory.
  • You may change the tree temporarily but must leave it as you found it.
  • You need to find something in sorted order of a search tree, like two swapped values, with constant memory.

Check yourself

Answer each one in your head first, then open it.

Why is the predecessor's right pointer always free to use?

The predecessor is the rightmost node of the left subtree, so it has no right child. Its right is null until we place the thread there.

How many times is a node with a left child visited?

Twice: once to tie the thread before going left, and once when the walk comes back through that thread. Nodes without a left child are visited once.

What happens if you forget pred.right = null?

The result can still be right, but the tree keeps loops. Any later walk that follows right pointers may circle forever.

In the trace, why does the predecessor search for 30 take no steps to the right?

30.left is 25, and 25 has no right child, so 25 itself is the rightmost node of that left subtree.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule: whenever the loop reaches current, every node before current's subtree in inorder is already in result, and every thread in the tree points from some node to the node that comes right after it in inorder, an ancestor still waiting for its left side to finish. At the start there are no threads and result is empty.

Each branch keeps the rule. With no left child, current is next in inorder, so recording it is right, and current.right leads either into its real right subtree or along a thread to the next node in inorder. With a left child and no thread yet, we add one thread from pred to current, which is correct because current comes right after pred in inorder. With the thread already there, we can only have arrived through it, so the left subtree was fully recorded and current is next.

Each node with a left child is reached exactly twice and every other node once, and the predecessor searches together walk each edge at most twice, once to tie a thread and once to untie it. So the loop ends after O(n) steps. Each thread is removed on the second visit, so when current becomes null the tree has its original shape and result holds all n values in order.

Going deeper

3 more ideas

Why the thread leads to the right place

In inorder, the node visited just before current is the last node of its left subtree, which is the rightmost one. Inorder would next visit current itself. So pointing that node's empty right at current makes "go right" mean "go to the next node in inorder", which is exactly what the walk needs.

Why it is still O(n) time

Finding a predecessor walks down a right edge of a left subtree. Each edge of the tree is walked this way at most twice: once to set a thread and once to remove it. So all the predecessor searches together cost O(n), and the whole walk is O(n) time with O(1) extra memory.

Never stop halfway

While the walk runs, the tree contains extra links, and some of them form loops. If you return early (say, after finding the k-th value), threads are left in place and other code that walks the tree may loop forever. Either finish the walk or remove the threads before leaving.

Work it by hand

Every step in a table, with why

Walk a 5-node search tree in order with no stack. Two nodes have a left child, so two threads are tied and later removed.

root = [20, 10, 30, null, 15, 25]

Stepcurrentpred walkThreadresultWhat happensWhy
12010, 15tie 15.right = 20[]go left to 1020 has a left child. Its predecessor is the rightmost node of the left subtree: start at 10, step right to 15. 15.right is null, so this is the first visit, and the thread is tied.
210--[10]record, go right to 1510 has no left child, so nothing comes before it. Record it and follow its real right child.
315--[10, 15]record, follow thread to 2015 has no left child. Record it. Its right is the thread, so "go right" climbs back to 20 without any stack.
42010, 15untie 15.right[10, 15, 20]record, go right to 30The predecessor walk stops at 15 because 15.right === current. So the left side is done: untie, record 20, go right.
53025tie 25.right = 30[10, 15, 20]go left to 2530 has a left child 25, which has no right child, so the predecessor is 25 itself. Tie the thread.
625--[10, 15, 20, 25]record, follow thread to 3025 has no left child. Record it, and its thread leads back up to 30.
73025untie 25.right[10, 15, 20, 25, 30]record, go right to nullBack at 30 through the thread. Untie it, record 30, and move to 30.right, which is null, so the loop ends.

[10, 15, 20, 25, 30] after 7 rounds of the loop: one per node, plus a second visit to each of the 2 nodes that have a left child. Both threads were removed, so the tree is [20, 10, 30, null, 15, 25] again, exactly as it started.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Morris traversalO(n)O(1)Memory must stay constant and nothing else reads the tree during the walk.
Iterative traversal with a stackO(n)O(h)The usual choice: no pointer changes, safe to stop early, easy to pause.
Recursive depth-first searchO(n)O(h)Short and clear when the tree is not too deep.

Extra memory: O(1) extra: only current and pred, whatever the tree's size. The output list adds O(n), and nothing else is stored.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Morris traversal and the other approaches, on a scale where each line up is 10 times more steps.
  • Morris traversal, Iterative traversal with a stack, Recursive depth-first search O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Morris traversal101,0001 million
Iterative traversal with a stack101,0001 million
Recursive depth-first search101,0001 million

Inputs that need care

5 tricky inputs
An empty tree: root = null
The while loop never runs, and the result is [].
A chain leaning left: 3, with left child 2, with left child 1
Each node's predecessor is its own left child, so the threads 2.right = 3 and 1.right = 2 are tied on the way down and untied on the way back. Every predecessor search is one step.
Leaving early, for example after the third value
Don't return inside the loop. Keep a counter, store the answer, and let the loop finish so every thread is removed. Otherwise the tree keeps loops, and later walks can run forever.
A predecessor loop without the pred.right !== current check
On the second visit, the search follows the thread back to current, then walks its left subtree again, forever. Both conditions are needed.
A tree shared with other code, or frozen with Object.freeze
Morris writes to right pointers. Other code reading the tree during the walk sees the threads, and on frozen nodes the writes fail, so the walk throws or gives wrong results. Use the stack walk instead.

Variations and follow-ups

Twists interviewers add

Morris preorder

Use the same threads, but record current on its first visit, right when the thread is tied, instead of on the second. Nodes without a left child are still recorded right away.

Find two swapped values in a search tree

If two values of a search tree were swapped by mistake, the inorder list has one or two spots where a value is bigger than the one after it. Morris finds them with O(1) memory by keeping only the previous value seen.

Morris postorder

It's possible but awkward: on the second visit to a node, output the right edge of its left subtree in reverse, which needs a temporary reversal of those right pointers. Most code uses a stack for postorder instead.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "O(1) extra space" together with "inorder" or "sorted order of a BST". Without that memory limit, a stack is simpler and usually preferred.
  • Explain the thread in one sentence: "the last node of my left subtree points back to me, so the walk can find its way up". Then show the two visits: the first ties the thread, the second unties it and records the node.
  • Trace a three-node tree by hand, a root whose left child has a right child, and say which pointer changes at each step. It shows you know the tree is restored.
  • Expect "why is it still O(n) when every node runs a predecessor loop?". The loops only walk right edges inside left subtrees, and each such edge is walked once to tie a thread and once to untie it.

Where frontend code uses it

The same idea in real UI code
  • React fiber nodes store child, sibling, and return (parent) pointers so the work loop can walk the component tree with a plain loop and no stack. Morris traversal uses the same idea: extra pointers replace the stack.
  • In memory-tight code, such as walking a large tree in a web worker on a low-end phone, an O(1) memory walk avoids allocating a stack as deep as the tree.

Related algorithms