Bird
Raised Fist0

Given the following partial recursion state during building a tree from inorder and postorder traversals, where the current root is 20, and the inorder segment is [15, 20, 7], postorder segment is [15, 7, 20], what is the original inorder array?

hard🔄 Reverse Engineer Q9 of Q15
Tree: Depth-First Search - Construct Tree from Inorder and Postorder
Given the following partial recursion state during building a tree from inorder and postorder traversals, where the current root is 20, and the inorder segment is [15, 20, 7], postorder segment is [15, 7, 20], what is the original inorder array?
A[7, 15, 20, 9, 3]
B[9, 3, 15, 20, 7]
C[15, 20, 7, 3, 9]
D[3, 9, 7, 15, 20]
Step-by-Step Solution
Solution:

  1. Step 1: Recognize inorder segment corresponds to subtree

    Current inorder segment [15, 20, 7] is a contiguous slice of original inorder.

  2. Step 2: Identify original inorder containing this segment

    [9, 3, 15, 20, 7] contains [15, 20, 7] as a contiguous segment in correct order.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Only [9, 3, 15, 20, 7] contains the segment in correct order [OK]
Quick Trick: Subtree inorder segment must appear contiguous in original inorder [OK]
Common Mistakes:
MISTAKES
  • Assuming segments can be non-contiguous
  • Ignoring traversal order
Trap Explanation:
PITFALL
  • Candidates often fail to map subtree segments back to original inorder correctly.
Interviewer Note:
CONTEXT
  • Tests deep understanding of recursion state and traversal segments.
Master "Construct Tree from Inorder and Postorder" 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
Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 10hard Binary Tree Postorder Traversal - Binary Tree Postorder Traversal - Quiz 2easy Binary Tree Postorder Traversal - Binary Tree Postorder Traversal - Quiz 12easy Construct Tree from Preorder and Inorder - Construct Tree from Preorder and Inorder - Quiz 13medium Diameter of Binary Tree - Diameter of Binary Tree - Quiz 13medium House Robber III (On Tree) - House Robber III (On Tree) - Quiz 8hard Invert Binary Tree - Invert Binary Tree - Quiz 8hard Lowest Common Ancestor of Binary Tree - Lowest Common Ancestor of Binary Tree - Quiz 13medium Path Sum - Path Sum - Quiz 8hard Serialize and Deserialize Binary Tree - Serialize and Deserialize Binary Tree - Quiz 10hard