Which approach correctly produces the inorder sequence without recursion or extra stack?
hard🎤 Interviewer Follow-up Q15 of Q15
Tree: Depth-First Search - Binary Tree Inorder Traversal
Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?
AUse Morris traversal by creating threads on parent pointers instead of child pointers.
BUse breadth-first search since parent pointers allow level order traversal.
CUse recursive traversal ignoring parent pointers, which will fail due to missing child links.
DUse iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.
Step-by-Step Solution
Step 1: Understand traversal constraints
Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
Step 2: Use parent pointers to simulate traversal
By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.
Final Answer:
Option D -> Option D
Quick Check:
Tracking previous node enables correct traversal without extra space [OK]
