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.