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.

worked-example

Consider tracing the algorithm step-by-step on a LeftChain4 tree where nodes are inserted in the sequence 4, 3, 2, 1. The tree is skewed to the left. The root is 4, its left child is 3, 3's left child is 2, and 2's left child is 1. We start the algorithm with current = 4. We define a single iteration as one full execution of the outer while loop (where current != null).

Iteration 1: current = 4. The left child is 3, which is not null. We find the inorder predecessor of 4 in its left subtree, which is 3 (the rightmost node in the subtree rooted at 3, which is just 3 itself as it has no right child). We create a thread setting its right pointer to the current node: 3->4. We move current = 4.left = 3.
Iteration 2: current = 3. The left child is 2, which is not null. We find the inorder predecessor of 3, which is 2. The predecessor's right is null, so we create a thread: 2->3. We move current = 3.left = 2.
Iteration 3: current = 2. The left child is 1, which is not null. The predecessor of 2 is 1. We create a thread: 1->2. We move current = 2.left = 1.
Iteration 4: current = 1. The left child is null. We visit 1, appending it to our inorder sequence. We then advance following the right pointer. Due to the thread installed in Iteration 3, 1.right = 2. Thus, we move current = 2.
Iteration 5: current = 2. The left child is 1, which is not null. We search for its predecessor starting from 1 and traversing right. We follow 1.right = 2, reaching current. Because the predecessor's right points to current, we know we have already visited the left subtree. We restore the tree by removing the thread (1.right = null), visit 2, and then move current = 2.right, which is 3 via its 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.

Open the Interactive Title.
Set Tree fixture to "Balanced7".
Set Inspected iterations to 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.

limitations

The primary limitation of Morris Traversal is that it temporarily modifies the tree structure. In a multithreaded environment or any scenario where concurrent reads of the tree are occurring, the temporary cycles introduced by threads will cause infinite loops or incorrect behavior for other processes. The tree is strictly not a valid binary search tree during the traversal, and its pointer state is only fully restored (pointerStateRestored = Yes) upon complete termination.

references

The algorithm was introduced by Joseph H. Morris in his paper on traversing binary trees without auxiliary stacks.

Traversing binary trees simply and cheaply (Morris, 1979) - The original paper detailing the O(1) space traversal algorithm by temporarily modifying leaf pointers.

Morris Inorder Temporary Thread Restoration