Bird
Raised Fist0

What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?

medium🪤 Complexity Trap Q13 of Q15
Tree: Depth-First Search - Binary Tree Preorder Traversal
What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?
AO(n log n) because each node is visited multiple times during threading
BO(n) but with O(n) auxiliary space due to recursion stack
CO(n^2) because the inner loop to find predecessor can traverse many nodes repeatedly
DO(n) because each edge is traversed at most twice during threading and restoration
Step-by-Step Solution
Solution:

  1. Step 1: Identify traversal of nodes and edges

    Each node is visited once, and each edge is traversed at most twice (once to create thread, once to remove it).

  2. Step 2: Explain why complexity is linear

    Because total edge traversals sum to O(n), the overall time complexity is O(n).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Threading and restoring links cause at most two visits per edge [OK]
Quick Trick: Each edge visited max twice -> O(n) time [OK]
Common Mistakes:
MISTAKES
  • Assuming inner loop causes O(n^2)
  • Confusing threading with recursion stack space
  • Thinking threading causes log n overhead
Trap Explanation:
PITFALL
  • The inner loop looks like nested iteration, tempting candidates to pick O(n^2), but total traversals are linear.
Interviewer Note:
CONTEXT
  • Checks understanding of Morris traversal's time complexity and why it is linear despite nested loops.
Master "Binary Tree Preorder Traversal" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes
Balanced Binary Tree - Balanced Binary Tree - Quiz 6medium Balanced Binary Tree - Balanced Binary Tree - Quiz 10hard Binary Tree Cameras - Binary Tree Cameras - Quiz 11easy Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 13medium Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 11easy Construct Tree from Inorder and Postorder - Construct Tree from Inorder and Postorder - Quiz 6medium Construct Tree from Preorder and Inorder - Construct Tree from Preorder and Inorder - Quiz 14medium Flatten Binary Tree to Linked List - Flatten Binary Tree to Linked List - Quiz 12easy Path Sum - Path Sum - Quiz 1easy Serialize and Deserialize Binary Tree - Serialize and Deserialize Binary Tree - Quiz 10hard