Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?

easy🧾 Code Trace Q12 of Q15

Tree: Depth-First Search - Construct Tree from Inorder and Postorder

Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?

Step-by-Step Solution

Step 1: Initialize variables
inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
Step 2: First iteration (i=3, node_val=20)
top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.
Step 3: Second iteration (i=2, node_val=7)
top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.
Step 4: Third iteration (i=1, node_val=15)
top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.
Final Answer:
Option D -> Option D
Quick Check:
inorder_index decremented twice after popping 7 and 20 [OK]

Quick Trick: inorder_index decrements only when popping matching nodes [OK]

Common Mistakes:

MISTAKES

Off-by-one error in inorder_index update
Confusing when to pop stack
Misreading top.val vs inorder[inorder_index]

Trap Explanation:

PITFALL

Candidates often forget inorder_index updates only on popping matching nodes, not on every iteration.

Interviewer Note:

CONTEXT

Tests ability to mentally simulate stack-based tree construction and index tracking.

Master "Construct Tree from Inorder and Postorder" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Tree: Depth-First Search Quizzes

Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?

Step 1: Initialize variables

Step 2: First iteration (i=3, node_val=20)

Step 3: Second iteration (i=2, node_val=7)

Step 4: Third iteration (i=1, node_val=15)

Final Answer:

Quick Check:

Want More Practice?