What is the time complexity of the Morris inorder traversal algorithm on a binary tree with n nodes?

medium🪤 Complexity Trap Q13 of Q15

Tree: Depth-First Search - Binary Tree Inorder Traversal

AO(n) because each edge is visited at most twice during threading and unthreading.

BO(n \times h) where h is tree height due to repeated traversal of left subtrees.

CO(n \log n) due to repeated searching for predecessors.

DO(n^2) in worst case when tree is skewed and predecessor search is costly.

Step-by-Step Solution

Step 1: Analyze predecessor visits
Each node's left subtree is traversed to find the predecessor, which can take up to h steps where h is the height of the tree.
Step 2: Count total operations
In skewed trees, this leads to O(n x h) time complexity due to repeated traversal of left subtrees.
Final Answer:
Option B -> Option B
Quick Check:
Worst-case time complexity is O(n x h) [OK]

Quick Trick: Predecessor search can take O(h) per node in skewed trees [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often think Morris traversal is always O(n), but worst case can be O(n x h) due to predecessor searches.

Interviewer Note:

CONTEXT

Master "Binary Tree Inorder Traversal" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Tree: Depth-First Search Quizzes