Tree Traversals
Every traversal visits the same nodes. The only thing that changes is when a node gets written down relative to its two subtrees. Morris walks the same inorder sequence with no stack at all: before descending into a left subtree it points the rightmost node of that subtree back at the current node, and when the walk arrives along that borrowed pointer it knows the left side is finished, removes the pointer and visits. The tree ends exactly as it started, and the extra memory is a single variable.
Walk this tree in inorder without a stack and without recursion. Both of those exist only to remember the way back up, so Morris borrows the empty right pointer of the node that comes just before the current one, points it at the current node, and follows it home later. Every borrowed pointer is put back, so the tree is unchanged at the end.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.
The predecessor of 50 is 40. What happens next?
Answer: No thread yet: point it back here and go left. An empty right pointer means the left subtree is still ahead, so thread it and go left. A pointer already aimed here means the left subtree is done, so take the thread out and visit.
The predecessor of 30 is 20. What happens next?
Answer: No thread yet: point it back here and go left. An empty right pointer means the left subtree is still ahead, so thread it and go left. A pointer already aimed here means the left subtree is done, so take the thread out and visit.
The predecessor of 30 is 20. What happens next?
Answer: The thread is back: remove it and visit this node. An empty right pointer means the left subtree is still ahead, so thread it and go left. A pointer already aimed here means the left subtree is done, so take the thread out and visit.
The predecessor of 50 is 40. What happens next?
Answer: The thread is back: remove it and visit this node. An empty right pointer means the left subtree is still ahead, so thread it and go left. A pointer already aimed here means the left subtree is done, so take the thread out and visit.
The predecessor of 70 is 60. What happens next?
Answer: No thread yet: point it back here and go left. An empty right pointer means the left subtree is still ahead, so thread it and go left. A pointer already aimed here means the left subtree is done, so take the thread out and visit.
The predecessor of 70 is 60. What happens next?
Answer: The thread is back: remove it and visit this node. An empty right pointer means the left subtree is still ahead, so thread it and go left. A pointer already aimed here means the left subtree is done, so take the thread out and visit.
How it runs, step by step
Walk this tree in inorder without a stack and without recursion. Both of those exist only to remember the way back up, so Morris borrows the empty right pointer of the node that comes just before the current one, points it at the current node, and follows it home later. Every borrowed pointer is put back, so the tree is unchanged at the end.
Morris inorder over 7 nodes, using threads instead of a stack.
50 has a left subtree, so something comes before it. Its inorder predecessor is 40, the rightmost node on its left. That node's right pointer is empty, so the left subtree has not been walked yet.
Predecessor of 50 is 40.
Point 40's empty right pointer at 50: that is the thread, and it is the only reason this walk can find its way back without a stack. Now go left to 30 and do the same there.
Thread 40 to 50, then move left.
30 has a left subtree, so something comes before it. Its inorder predecessor is 20, the rightmost node on its left. That node's right pointer is empty, so the left subtree has not been walked yet.
Predecessor of 30 is 20.
Point 20's empty right pointer at 30: that is the thread, and it is the only reason this walk can find its way back without a stack. Now go left to 20 and do the same there.
Thread 20 to 30, then move left.
20 has no left child, so nothing comes before it: visit it now and move along the thread back up to 30.
Visit 20.
30 has a left subtree, so something comes before it. Its inorder predecessor is 20, the rightmost node on its left. That node's right pointer already points back here, which can only mean the left subtree is finished and the walk has climbed back.
Predecessor of 30 is 20.
Take the thread out of 20, which puts the tree back exactly as it was, and visit 30: everything smaller has been seen. Now into its right subtree, starting at 40.
Unthread 20 and visit 30.
40 has no left child, so nothing comes before it: visit it now and move along the thread back up to 50.
Visit 40.
50 has a left subtree, so something comes before it. Its inorder predecessor is 40, the rightmost node on its left. That node's right pointer already points back here, which can only mean the left subtree is finished and the walk has climbed back.
Predecessor of 50 is 40.
Take the thread out of 40, which puts the tree back exactly as it was, and visit 50: everything smaller has been seen. Now into its right subtree, starting at 70.
Unthread 40 and visit 50.
70 has a left subtree, so something comes before it. Its inorder predecessor is 60, the rightmost node on its left. That node's right pointer is empty, so the left subtree has not been walked yet.
Predecessor of 70 is 60.
Point 60's empty right pointer at 70: that is the thread, and it is the only reason this walk can find its way back without a stack. Now go left to 60 and do the same there.
Thread 60 to 70, then move left.
60 has no left child, so nothing comes before it: visit it now and move along the thread back up to 70.
Visit 60.
70 has a left subtree, so something comes before it. Its inorder predecessor is 60, the rightmost node on its left. That node's right pointer already points back here, which can only mean the left subtree is finished and the walk has climbed back.
Predecessor of 70 is 60.
Take the thread out of 60, which puts the tree back exactly as it was, and visit 70: everything smaller has been seen. Now into its right subtree, starting at 80.
Unthread 60 and visit 70.
80 has no left child, so nothing comes before it: visit it now and move to its right, which is empty, so the walk is over.
Visit 80.
The walk is 20, 30, 40, 50, 60, 70, 80, sorted, because inorder on a search tree always is. It used 3 temporary threads and no stack, so the extra memory is O(1) rather than the O(h) a recursive walk needs, and every thread was removed again: the tree is exactly as it started. The cost is that each edge is walked at most twice, and that the tree is briefly modified, which makes Morris unsafe to run from two threads at once.
Morris visited 20, 30, 40, 50, 60, 70, 80 using 3 threads.
Remember
- Inorder on a search tree comes out sorted, which is the fastest way to check one is valid.
- Pre, in and post differ only in where visit sits among the two recursive calls.
- Level order is the odd one out: it needs a queue rather than the call stack. Morris needs neither, by threading each subtree's rightmost node back to its owner and removing it again.
Topics covered
Related
Where this is used
CompilersAST visitors in Babel and ESLint
A plugin registers enter and exit handlers for a node type: enter fires on the way down, which is preorder, and exit fires on the way back up, which is postorder. A transform that rewrites a node out of its already-rewritten children has to run in exit, because at enter the children have not been touched yet. Picking the wrong hook is a common plugin bug.
Operationsdu, rm -r and find -depth
A directory's size is unknown until every child has been measured, so du has to report postorder. rm -r has the same shape for a different reason: a directory cannot be unlinked while it still holds entries. find walks preorder by default and offers -depth to switch to postorder, which is why -delete turns -depth on for you.
GraphicsLayout in Flutter and browser engines
Layout is two directions over one tree. Constraints travel down in preorder, sizes come back up in postorder because a column cannot know its own height until every child has reported one, and the parent then sets each child's position now that it knows the size. A single pass in either direction alone would not have the information it needs.
Language runtimesGarbage collector marking
A tracing collector walks the object graph to find what is still reachable, and it typically runs when memory is already tight, which is the worst moment to allocate a traversal stack. Pointer reversal, the Deutsch-Schorr-Waite scheme, takes Morris's bargain: it temporarily flips the pointer it arrived on so the object itself records the way back, then restores it on the way out. No stack that grows with the depth of the heap, and the pointers are left exactly as they were found.
Why it works this way
Why level order needs a queue when the other three do not
Pre, in and post only ever need to get back to an ancestor, and the call stack already holds that path for free. Level order needs the node to the right at the same depth, which is not an ancestor and sits nowhere on the current path, so nothing on the stack can supply it. The queue is the explicit store for nodes that have been seen but not yet visited, kept in the order they were seen.
Why reverse level order enqueues the right child first
A stack hands back whatever order it was filled in, reversed. Filling it top to bottom and left to right would pop bottom to top but right to left, which is not what you want. Pushing the right child first makes the queue emit each level right to left, and reversing that lands on the bottom level first, left to right.
The recursive space bound is O(h), and h can be n
On a balanced tree the recursion is about log n frames deep, which costs nothing. A tree built by inserting already-sorted keys is a single chain, so h equals n and the traversal needs one frame per node. A few tens of thousands of nodes is enough to overflow a default JVM thread stack, which is the real reason an explicit stack or Morris is worth knowing. The breadth-first walks do not have this bound at all: their queue holds a whole level, so their cost is the width of the tree, and on a balanced tree the widest level is about half the nodes.
Morris leaves the tree temporarily broken
While the walk is in progress, some right pointers point back up at an ancestor, so the structure is not a tree: a reader that follows one of those borrowed pointers is sent back to a node it has already passed and can loop forever. It also cannot be abandoned halfway, since breaking out of the loop early leaves those threads in place, and it will not run on a tree you are only allowed to read. Finding each predecessor walks the right spine of a left subtree, so some edges are crossed up to three times, but that is a constant factor and the total stays O(n).
Read more
- Tree traversalWikipedia
- Threaded binary treeWikipedia
- Breadth-first searchcp-algorithms
- Binary search tree visualisedUSF
- Layout constraints: sizes go up, positions come from the parentFlutter
Next up
- BST Range SearchReport every value in a range, entering only the subtrees that could hold one.
- Validate BSTEvery node must sit inside a window inherited from all its ancestors, not just its parent.
- BST Reconstruction from PreorderKeep a stack of nodes with an open right side; a smaller value is the top's left child, a larger one the right child of the last node popped.