Morris Traversal : Traverse/ Flatten Tree into LinkedList in O(1) space
If I ask you to traverse a Binary Tree : you will either do it recursively or by using a stack. In both cases you use O(tree_ht) space complexity.
👉🏻 Follow-up: Interviewer asks you to traverse Tree in O(1) space. What do you do?
✅ Takeaway: Whenever interviewer asks you to traverse a Tree in O(1) space or convert/ flatten a Tree to Linked List → blindly apply Morris Traversal
✅ Basic Concept of Morris:
- ➡️ While curr_node.left exists, we get the predecessor of curr_node and make it’s right pointer point to curr_node.
- ➡️ Now we can safely get rid of curr_node’s left pointer as we have memoized the information contained in this pointer into predecessor_node’s right pointer
👉🏻 Now, Morris Traversal can be done in 2 ways : In-order and Pre-order
👉🏻 The above 2 questions will use Pre-order traversal in Morris:
- ➡️ After finding predecessor of current_node, we set predecessors’s right pointer to be current_node’s right node.
- ➡️ And then we adjust current_node’s pointer to make its left = Null and right = left_child, and then update value of current_node to it’s previous left_child
👉🏻 This questions utilise In-order Traversal in Morris:
- ➡️ We find predecessor of current_node, ans set predecessor’s right to be current_node
- ➡️ And then once all the left nodes of current_node have been processed, we set current_node’s right to be the successor of current_node, and then update current_node to it’s previous right child
🧠 Morris Traversal is pretty tricky to implement and I would certainly suggest to practice the above questions over and over till the pointer manipulation in Morris is imprinted in your brain.
