Given the following code snippet for building a binary tree from preorder and inorder traversals, what is the value of inorder_index after processing the second element of preorder = [3,9,20] and inorder = [9,3,20]?

easy🧾 Code Trace Q12 of Q15

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

Given the following code snippet for building a binary tree from preorder and inorder traversals, what is the value of inorder_index after processing the second element of preorder = [3,9,20] and inorder = [9,3,20]?

Step-by-Step Solution

Step 1: Initialize variables
Start with root=3, stack=[3], inorder_index=0 (inorder[0]=9).
Step 2: Process second preorder element (9)
Top of stack is 3, which is not equal to inorder[0]=9, so 9 becomes left child of 3 and is pushed to stack. inorder_index remains 0.
Step 3: Process third preorder element (20)
Top of stack is 9, which equals inorder[0]=9, so pop 9 and increment inorder_index to 1. Now top is 3, equals inorder[1]=3, pop 3 and increment inorder_index to 2. Then 20 becomes right child of 3 and is pushed to stack.
Final Answer:
Option A -> Option A
Quick Check:
inorder_index increments twice after processing 20, so after second element it is 1 [OK]

Quick Trick: inorder_index increments only when stack top matches inorder element [OK]

Common Mistakes:

MISTAKES

Off-by-one increment of inorder_index
Confusing preorder and inorder indices
Forgetting to pop stack before incrementing inorder_index

Trap Explanation:

PITFALL

Candidates often forget that inorder_index increments only after popping matching nodes, not immediately.

Interviewer Note:

CONTEXT

Tests ability to mentally simulate iterative tree construction code.

Master "Construct Tree from Preorder and Inorder" 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 binary tree from preorder and inorder traversals, what is the value of inorder_index after processing the second element of preorder = [3,9,20] and inorder = [9,3,20]?

Step 1: Initialize variables

Step 2: Process second preorder element (9)

Step 3: Process third preorder element (20)

Final Answer:

Quick Check:

Want More Practice?