Morris Traversal Algorithm (Binary Tree Traversal)

Description
The Morris traversal algorithm is an algorithm that can complete binary tree traversal in O(n) time using only O(1) extra space. It avoids using a stack or recursion by temporarily modifying pointers within the tree (which are restored after traversal). It is suitable for in-order and pre-order traversals (post-order traversal is more complex). The core idea is to utilize the null pointers of leaf nodes to point to successor nodes, allowing the traversal to backtrack to upper-level nodes.

Problem-Solving Process

1. Problem Analysis

   • Conventional binary tree traversal (recursive/iterative) requires O(h) stack space (where h is the tree height).
   • Morris traversal uses the concept of a threaded binary tree, employing idle pointers to record the backtracking path, achieving O(1) space complexity.

2. Steps of the Morris Algorithm for In-order Traversal

   • Initialize the current node cur as the root node.
   • Loop while cur is not null:
     • If cur has no left subtree:
       • Output the value of cur (visit the current node).
       • Set cur to point to the right subtree (cur = cur.right).
     • If cur has a left subtree:
       • Find cur's predecessor node pre (i.e., the rightmost node in the left subtree):
         • pre = cur.left
         • Move pre to the right repeatedly until pre.right is null or points to cur (to avoid infinite loops).
       • If pre.right is null:
         • Set pre.right to point to cur (create a temporary backtracking pointer).
         • Move cur to the left (cur = cur.left).
       • If pre.right points to cur (indicating the left subtree has already been visited):
         • Remove the temporary pointer: pre.right = null.
         • Output the value of cur (the left subtree has been processed at this point).
         • Move cur to the right (cur = cur.right).

3. Example Demonstration (In-order Traversal)
   Take the binary tree [1,2,3,4,5] as an example (root is 2, left subtree is 1, right subtree is 4, with children 3 and 5):

   • Step 1: cur=2, left subtree exists, find predecessor node 1 (the rightmost node), set 1.right to point to 2.
   • Step 2: cur=1, no left subtree, output 1, move cur to 1.right (i.e., 2).
   • Step 3: cur=2, left subtree exists and predecessor 1.right points to 2, remove the pointer, output 2, move cur to the right subtree 4.
   • Step 4: cur=4, left subtree exists, find predecessor node 3, set 3.right to point to 4.
   • Step 5: cur=3, no left subtree, output 3, move cur to 3.right (i.e., 4).
   • Step 6: cur=4, left subtree exists and predecessor 3.right points to 4, remove the pointer, output 4, move cur to the right subtree 5.
   • Step 7: cur=5, no left subtree, output 5, traversal ends.
     The output order is 1,2,3,4,5 (correct in-order).

4. Adjustment for Pre-order Traversal

   • Difference from in-order traversal: Output the node immediately upon first access (i.e., before creating the temporary pointer).
   • Adjusted steps:
     • When cur has a left subtree and predecessor pre.right is null, output cur and create the pointer.
     • When cur has no left subtree, output cur and then move directly to the right.

5. Key Points Summary

   • Time Complexity: Each node is visited twice (once to find the predecessor, once during traversal), but each predecessor node is found at most twice, resulting in a total number of operations of O(n).
   • Space Complexity: Only constant extra variables are used (O(1)).
   • Important Notes: The algorithm temporarily modifies pointers during traversal but restores the original tree structure afterward (temporary pointers are automatically removed).

Through the Morris algorithm, space usage can be greatly optimized without sacrificing time complexity, making it especially suitable for scenarios with strict space constraints (e.g., embedded systems).