[Solved] Examine the recursive DFS code below for finding LCA. What is the logical error that causes incorrect results when one node is ancestor of the other?def LCA(root, p, q): if not root:... | Tree: Depth-First Search

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

Examine the recursive DFS code below for finding LCA. What is the logical error that causes incorrect results when one node is ancestor of the other?

def LCA(root, p, q):
    if not root:
        return None
    if root == p or root == q:
        return root
    left = LCA(root.left, p, q)
    right = LCA(root.right, p, q)
    if left and right:
        return root
    return left or right

AReturns root prematurely when root matches p or q without checking subtrees

BNo error; code correctly handles ancestor-descendant cases

CFails to check if both left and right are None before returning

DDoes not handle the case when p and q are the same node

Step-by-Step Solution

Solution:

Step 1: Base case returns root if matches p or q
This correctly identifies if current node is one of the targets.
Step 2: Recursively search left and right subtrees
Left and right calls find p or q in subtrees.
Step 3: If both sides return non-null, current root is LCA
This covers ancestor-descendant and sibling cases.
Final Answer:
Option B -> Option B
Quick Check:
Code correctly handles ancestor-descendant [OK]

Quick Trick: Returning root on match is correct base case [OK]

Common Mistakes:

MISTAKES

Assuming premature return causes error
Overcomplicating ancestor-descendant handling

Trap Explanation:

PITFALL

Misreading base case as bug when it is correct

Interviewer Note:

CONTEXT

Tests ability to analyze correctness of standard recursive LCA code

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

More Tree: Depth-First Search Quizzes

Examine the recursive DFS code below for finding LCA. What is the logical error that causes incorrect results when one node is ancestor of the other?

Step 1: Base case returns root if matches p or q

Step 2: Recursively search left and right subtrees

Step 3: If both sides return non-null, current root is LCA

Final Answer:

Quick Check:

Want More Practice?