Recall & Review
beginner
What is the main advantage of Morris Traversal for inorder tree traversal?
Morris Traversal uses no extra space like stack or recursion. It modifies the tree temporarily to achieve inorder traversal with O(1) space.
Click to reveal answer
intermediate
In Morris Traversal, what is the purpose of creating a temporary thread (link) from the rightmost node of the left subtree to the current node?
This temporary thread helps to return to the current node after finishing the left subtree traversal without using a stack or recursion.
Click to reveal answer
intermediate
What happens when the temporary thread in Morris Traversal is encountered again during traversal?
When the thread is encountered again, it means the left subtree is fully visited. The thread is removed, and the current node is processed (printed). Then traversal moves to the right subtree.
Click to reveal answer
beginner
Show the basic steps of Morris Traversal inorder algorithm.
- Initialize current as root.
- If current has no left child, print current and move to right child.
- If current has left child, find rightmost node in left subtree.
- If rightmost node's right is null, make it point to current (thread) and move current to left child.
- If rightmost node's right points to current, remove thread, print current, move to right child.
Click to reveal answer
beginner
Why is Morris Traversal considered efficient in terms of space compared to recursive or stack-based inorder traversal?
Because it does not use extra memory for stack or recursion call stack. It only uses the tree's existing pointers temporarily, achieving O(1) space complexity.
Click to reveal answer
What data structure does Morris Traversal avoid using for inorder traversal?
✗ Incorrect
Morris Traversal avoids using a stack by creating temporary threads in the tree.
In Morris Traversal, what is the temporary link called that connects the rightmost node of the left subtree to the current node?
✗ Incorrect
The temporary link is called a thread, used to return to the current node after left subtree traversal.
What is the time complexity of Morris Traversal inorder traversal?
✗ Incorrect
Morris Traversal visits each node a constant number of times, so time complexity is O(n).
What happens to the temporary thread after the left subtree is fully traversed in Morris Traversal?
✗ Incorrect
The temporary thread is removed to restore the original tree structure.
Which traversal order does Morris Traversal implement without stack or recursion?
✗ Incorrect
Morris Traversal is mainly used for inorder traversal without extra space.
Explain how Morris Traversal achieves inorder traversal without using a stack or recursion.
Think about how the traversal remembers where to return after left subtree.
You got /4 concepts.
Describe the steps to find the rightmost node in the left subtree during Morris Traversal and how it is used.
Focus on how the rightmost node helps in creating and removing threads.
You got /4 concepts.