Given the following partial parent map after building it for a binary tree: parent = {node3: None, node5: node3, node1: node3, node6: node5, node2: node5} If the LCA of nodes 6 and 2 is node5, which nodes are the original p and q used in the LCA call?

hard🔄 Reverse Engineer Q9 of Q15

Tree: Depth-First Search - Lowest Common Ancestor of Binary Tree

Ap = node3, q = node1

Bp = node6, q = node2

Cp = node5, q = node3

Dp = node6, q = node1

Step-by-Step Solution

Solution:

Step 1: Analyze parent map
Nodes 6 and 2 have parent 5, so their LCA is node5.
Step 2: Identify p and q
p and q must be nodes 6 and 2 to have LCA node5.
Final Answer:
Option B -> Option B
Quick Check:
Only nodes 6 and 2 share LCA node5 [OK]

Quick Trick: LCA is common parent of p and q [OK]

Common Mistakes:

MISTAKES

Confusing parent map entries with p and q

Trap Explanation:

PITFALL

Candidates confuse parent map keys with query nodes.

Interviewer Note:

CONTEXT

Tests reverse reasoning from parent map to input nodes

Master "Lowest Common Ancestor of Binary Tree" 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 partial parent map after building it for a binary tree: parent = {node3: None, node5: node3, node1: node3, node6: node5, node2: node5} If the LCA of nodes 6 and 2 is node5, which nodes are the original p and q used in the LCA call?

Step 1: Analyze parent map

Step 2: Identify p and q

Final Answer:

Quick Check:

Want More Practice?