Lowest Common Ancestor in Binary Tree in DSA Python - Execution Trace

Concept Flow - Lowest Common Ancestor in Binary Tree

Start at root

↓

Check if root is None or matches p or q

↓

Search left subtree

↓

Search right subtree

↓

If both left and right return non-null

↓

Current node is LCA

↓

Return LCA

↓

Else return non-null child or None

Start from the root, search left and right subtrees recursively. If both sides find one target node each, current node is the lowest common ancestor.

Execution Sample

DSA Python

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

This code finds the lowest common ancestor of nodes p and q in a binary tree by recursive search.

Execution Table

Step	Operation	Node Visited	Left Result	Right Result	LCA Decision	Visual State
1	Start at root	3	?	?	Search left and right	3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
2	Check root == p or q	3	?	?	No, continue	Same as step 1
3	Search left subtree	5	?	?	Search left and right	Same as step 1
4	Check node 5 == p or q	5	?	?	Yes, node 5 is p	Same as step 1
5	Return node 5 up	5	5	?	Return 5	Same as step 1
6	Search right subtree	1	?	?	Search left and right	Same as step 1
7	Check node 1 == p or q	1	?	?	No, continue	Same as step 1
8	Search left subtree	0	?	?	Search left and right	Same as step 1
9	Check node 0 == p or q	0	?	?	No, continue	Same as step 1
10	Search left subtree	None	None	None	Return None	Same as step 1
11	Search right subtree	None	None	None	Return None	Same as step 1
12	Return None up from 0	0	None	None	Return None	Same as step 1
13	Search right subtree	8	?	?	Search left and right	Same as step 1
14	Check node 8 == p or q	8	?	?	No, continue	Same as step 1
15	Search left subtree	None	None	None	Return None	Same as step 1
16	Search right subtree	None	None	None	Return None	Same as step 1
17	Return None up from 8	8	None	None	Return None	Same as step 1
18	Return None up from 1	1	None	None	Return None	Same as step 1
19	At root 3, left=5, right=None	3	5	None	Left non-null, return 5	Same as step 1
20	Final LCA found: 5	3	5	None	Return 5 as LCA	Same as step 1

💡 Returned node 5 as lowest common ancestor because left subtree returned p and right subtree returned None

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 12	After Step 18	Final
root	3	5	5	0	1	3
left	?	5	5	None	None	5
right	?	?	?	None	None	None
LCA	None	None	None	None	None	5

Key Moments - 3 Insights

Why do we return the node immediately if root matches p or q?

Because if the current node is p or q, it could be the ancestor. See step 4 where node 5 matches p and is returned immediately.

Why do we return left or right if only one is non-null?

Because if only one subtree contains p or q, that subtree's result bubbles up. See step 19 where left=5 and right=None, so 5 is returned.

Why is the current node the LCA if both left and right are non-null?

Because it means p and q are found in different subtrees, so current node is their lowest common ancestor. This is shown in the general flow but not in this example.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the node visited and what decision is made?

A Node 5 visited, matches p, return node 5

B Node 3 visited, no match, continue search

C Node 1 visited, no match, continue search

D Node 0 visited, no match, return None

💡 Hint

Check step 4 in execution_table where node 5 is visited and matches p

At which step does the function return the final lowest common ancestor?

A Step 12

B Step 19

C Step 20

D Step 5

💡 Hint

Look at the exit_note and step 20 in execution_table for final LCA return

If node q was in the right subtree of node 1, how would the LCA decision change at root 3?

A Left and right both null, return None

B Both left and right would be non-null, so root 3 is LCA

C Left would be null, right non-null, so return right

D Left non-null, right null, return left

💡 Hint

Recall from concept_flow that if both left and right are non-null, current node is LCA

Concept Snapshot

Lowest Common Ancestor (LCA) in Binary Tree:
- Start at root node
- If root is None or matches p or q, return root
- Recursively search left and right subtrees
- If both sides return non-null, current node is LCA
- Else return non-null child or None
- Returns the lowest node that has both p and q as descendants

Full Transcript

The Lowest Common Ancestor algorithm starts at the root of the binary tree. If the root is None or matches one of the target nodes p or q, it returns the root immediately. Otherwise, it recursively searches the left and right subtrees. If both left and right recursive calls return non-null nodes, it means p and q are found in different subtrees, so the current node is their lowest common ancestor. If only one side returns a non-null node, that node is returned upwards. The process continues until the LCA is found or the search ends. This method ensures the lowest node containing both p and q is returned.

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The root node of the binary tree

B. The node with the smallest value between the two nodes

C. The deepest node that is an ancestor of both nodes

D. The parent node of the first node

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the deepest node in the tree that has both given nodes as descendants.

2. Step 2: Compare options with definition

   The deepest node that is an ancestor of both nodes matches the definition exactly. Other options describe different nodes.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option C

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the deepest shared parent node [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the smaller value node
• Assuming LCA is always the parent of one node

2. Which of the following is the correct Python function signature to find LCA in a binary tree node class named TreeNode?

easy

A. def find_lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

B. def find_lca(root, p, q): return int

C. def find_lca(root: int, p: int, q: int) -> TreeNode:

D. def find_lca(root: TreeNode, p: TreeNode, q: TreeNode): return str

Solution

1. Step 1: Check parameter types and return type

   The function should accept three TreeNode objects and return a TreeNode object representing the LCA.

2. Step 2: Match with options

   def find_lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: correctly uses type hints for parameters and return type. Others have wrong types or return types.

3. Final Answer:

   def find_lca(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: -> Option A

4. Quick Check:

   Correct signature uses TreeNode and returns TreeNode [OK]

Hint: Use TreeNode type hints for nodes and return [OK]

Common Mistakes:

• Using int instead of TreeNode for parameters
• Returning wrong type like int or str
• Omitting return type annotation

3. Given the following binary tree and code, what will be the output?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

# Tree:
#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4

root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

p = root.left  # Node 5
q = root.left.right.right  # Node 4

ancestor = lowestCommonAncestor(root, p, q)
print(ancestor.val)

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Trace recursive calls for nodes 5 and 4

   Node 5 is root.left, node 4 is root.left.right.right. The LCA is the lowest node that has both as descendants. Node 5 is an ancestor of node 4.

2. Step 2: Identify the LCA node

   Since 5 is ancestor of 4, LCA is node 5 itself.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   LCA(5,4) = 5 [OK]

Hint: If one node is ancestor of other, LCA is that node [OK]

Common Mistakes:

• Choosing root (3) instead of ancestor node
• Confusing node values with LCA
• Ignoring that node can be ancestor of itself

4. The following code attempts to find the LCA but has a bug. What is the error?

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

# Bug: The function sometimes returns None even if both nodes exist in tree.

medium

A. The function should not return root when left and right are both found

B. The function does not check if both nodes exist in the tree before returning

C. The function should return left and right together instead of root when both exist

D. The base case should return root instead of None when root is None

Solution

1. Step 1: Analyze base cases and recursive returns

   The function returns None if root is None, and returns root if root matches p or q. It then searches left and right subtrees.

2. Step 2: Identify missing check for node existence

   If one node is not in the tree, the function may return None incorrectly. It does not verify both nodes exist before returning LCA.

3. Final Answer:

   The function does not check if both nodes exist in the tree before returning -> Option B

4. Quick Check:

   Missing node existence check causes None returns [OK]

Hint: Verify both nodes exist before returning LCA [OK]

Common Mistakes:

• Assuming both nodes always exist in tree
• Changing base case to return root when root is None
• Returning root incorrectly when both left and right found

5. You have a binary tree where nodes can have duplicate values. How should you modify the LCA function to correctly find the LCA of two nodes p and q given only their values (not references)?

hard

A. Modify the function to find all nodes with given values and find LCA of all pairs

B. Use node references instead of values to avoid ambiguity

C. Modify the function to search nodes by value and return the first matching node found

D. Return the root node always since duplicates confuse the search

Solution

1. Step 1: Understand problem with duplicate values

   When values are duplicated, searching by value alone can find multiple nodes, so LCA must consider all matching nodes.

2. Step 2: Modify approach to handle duplicates

   Find all nodes matching p and q values, then compute LCA for each pair to find the correct lowest common ancestor.

3. Final Answer:

   Modify the function to find all nodes with given values and find LCA of all pairs -> Option A

4. Quick Check:

   Handle duplicates by checking all matching nodes [OK]

Hint: Check all nodes with values to handle duplicates [OK]

Common Mistakes:

• Using only first found node causing wrong LCA
• Assuming node references are always available
• Returning root node incorrectly for duplicates