Motivation
Describe your change:
Checklist:
Examples
Traversal order (Inorder: Left → Root → Right):
Step 1: Visit leftmost node → 3
Step 2: Back to parent → 5
Step 3: Move to right subtree → 6
Step 4: Right child of 6 → 9
Step 5: Back to root → 7
Step 6: Right child of root → 8
Final output sequence:
3, 5, 6, 9, 7, 8
Possible workarounds
Possible Workarounds – Conceptual Illustration
Method | Space Complexity | Notes
-- | -- | --
Recursive Inorder Traversal | O(h) | Uses call stack; simple but not O(1)
Iterative Inorder with Stack | O(h) | Explicit stack; simulates recursion
Threaded Binary Tree | O(1) | Permanently modifies tree pointers for threads
Visual analogy:
-
Recursive / Stack → climbing stairs with a backpack (stack grows with height).
-
Morris Traversal → climbing stairs using only your hands on rails (no extra backpack).
-
Threaded Tree → installing permanent rails on stairs (extra setup, but efficient traversal).
Additional information
Additional Information – Illustration
Key Points about Morris Traversal:
Memory Efficient: Uses O(1) extra space, unlike recursion or stack.
Inorder Traversal: Left → Root → Right.
Temporary Tree Modification: Creates “threads” to revisit nodes.
Future Extension: Preorder Morris Traversal is possible with minor changes.
Reference: Wikipedia → Threaded binary tree / Morris Traversal.
Conceptual Analogy:
Normal Traversal (Stack/Recursion) → Carrying bags for each level
Morris Traversal → Using built-in tree connections temporarily, no bags
Threaded Tree → Installing permanent pathways for future traversals
Motivation
Examples
Traversal order (Inorder: Left → Root → Right):
Step 1: Visit leftmost node → 3
Step 2: Back to parent → 5
Step 3: Move to right subtree → 6
Step 4: Right child of 6 → 9
Step 5: Back to root → 7
Step 6: Right child of root → 8
Final output sequence:
3, 5, 6, 9, 7, 8
Possible workarounds
Possible Workarounds – Conceptual Illustration
Visual analogy:
Recursive / Stack → climbing stairs with a backpack (stack grows with height).
Morris Traversal → climbing stairs using only your hands on rails (no extra backpack).
Threaded Tree → installing permanent rails on stairs (extra setup, but efficient traversal).
Additional information
Additional Information – Illustration
Key Points about Morris Traversal:
Memory Efficient: Uses O(1) extra space, unlike recursion or stack.
Inorder Traversal: Left → Root → Right.
Temporary Tree Modification: Creates “threads” to revisit nodes.
Future Extension: Preorder Morris Traversal is possible with minor changes.
Reference: Wikipedia → Threaded binary tree / Morris Traversal.
Conceptual Analogy:
Normal Traversal (Stack/Recursion) → Carrying bags for each level
Morris Traversal → Using built-in tree connections temporarily, no bags
Threaded Tree → Installing permanent pathways for future traversals