Morris Inorder Temporary Thread Restoration

Morris Traversal enables inorder traversal of a binary search tree in O(n) time with O(1) extra space. Instead of using a call stack for recursion or a stack data structure, the algorithm modifies the tree in-place by temporarily linking the rightmost node of a left subtree (the predecessor) to the current node. These temporary links are called threads. Crucially, as the traversal progresses, it visits the nodes and identifies when a thread has been followed, restoring the tree entirely back to its original state by removing the thread.

experiment

To see the intermediate cyclic pointer state and how threads are installed and restored, we can run the simulation and pause it at different iterations.

1. Open the Interactive Title.
2. Set Tree fixture to "Balanced7".
3. Set Inspected iterations to 4.
4. Observe the active threads 3->4 and the visited nodes sequence. Notice how threads that point back up to the current node are identified and subsequently removed to restore the tree's original structure.