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 zigzag order: one level at a time, alternating left to right and right to left.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
Which value is written down next?
Answer: 50. 50 is next in zigzag order. 20 is what inorder would take.
Which value is written down next?
Answer: 70. 70 is next in zigzag order. 30 is what inorder would take; 40 is what postorder would take.
Which value is written down next?
Answer: 30. 30 is next in zigzag order. 40 is what inorder would take; 20 is what preorder would take; 70 is what level-order would take; 60 is what reverse-level would take.
Which value is written down next?
Answer: 20. 20 is next in zigzag order. 50 is what inorder would take; 40 is what preorder would take; 60 is what postorder would take; 80 is what reverse-level would take.
Which value is written down next?
Answer: 40. 40 is next in zigzag order. 60 is what inorder would take; 70 is what preorder would take; 80 is what postorder would take; 30 is what reverse-level would take.
Which value is written down next?
Answer: 60. 60 is next in zigzag order. 70 is what inorder would take.
Which value is written down next?
Answer: 80. 80 is next in zigzag order. 50 is what postorder would take.
How it runs, step by step
Walk this tree in zigzag order: one level at a time, alternating left to right and right to left.
A binary search tree with 7 nodes. Walking it in zigzag order, which visits one level at a time, alternating left to right and right to left.
50 is the root, and level order starts at the top.
Visiting 50, number 1 of 7. The order so far is 50.
70 is next on its level, which this time is read right to left.
Visiting 70, number 2 of 7. The order so far is 50, 70.
30 is next on its level, which this time is read right to left.
Visiting 30, number 3 of 7. The order so far is 50, 70, 30.
20 is next on its level, which this time is read left to right.
Visiting 20, number 4 of 7. The order so far is 50, 70, 30, 20.
40 is next on its level, which this time is read left to right.
Visiting 40, number 5 of 7. The order so far is 50, 70, 30, 20, 40.
60 is next on its level, which this time is read left to right.
Visiting 60, number 6 of 7. The order so far is 50, 70, 30, 20, 40, 60.
80 is next on its level, which this time is read left to right. That is the last one.
Visiting 80, number 7 of 7. The order so far is 50, 70, 30, 20, 40, 60, 80.
The zigzag walk is 50, 70, 30, 20, 40, 60, 80.
The zigzag traversal visited 50, 70, 30, 20, 40, 60, 80.
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.