Morris Traversal
O(1)-space traversal by temporarily threading each node's inorder predecessor to it.
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.
What you will see
Temporary "thread" edges appear from rightmost leaves back up, then are removed.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Nodes announce value, left child and right child; each step announces the comparison and the direction taken or the structural change.
Reduced motion: Focus jumps node to node with a static ring; rotations become a crossfade between the two layouts.
Before this
Variants
- Morris Inorder Thread predecessor to node.
- Morris Preorder Output on thread creation.
- Morris Postorder Via a dummy root and reversed right chains.
Taught by the same lesson
Tree Traversals covers these too, in the same run.