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

Concept Flow - Lowest Common Ancestor in Binary Tree

Start at root node

↓

Check if root is null or matches p or q

Yes↓

Return root

No↓

Recurse left subtree

↓

Recurse right subtree

↓

If left and right both non-null

↓

Return root as LCA

↓

Return non-null child (left or right)

Start from root, check if root is p or q or null, else recurse left and right. If both sides return nodes, root is LCA. Otherwise return the non-null side.

Execution Sample

DSA Rust

fn lowest_common_ancestor(root: Option<&Box<TreeNode>>, p: i32, q: i32) -> Option<&Box<TreeNode>> {
    if root.is_none() || root.as_ref()?.val == p || root.as_ref()?.val == q {
        return root;
    }
    let left = lowest_common_ancestor(root.as_ref()?.left.as_ref(), p, q);
    let right = lowest_common_ancestor(root.as_ref()?.right.as_ref(), p, q);
    if left.is_some() && right.is_some() {
        return root;
    }
    left.or(right)
}

This function finds the lowest common ancestor of nodes with values p and q in a binary tree.

Execution Table

Step	Operation	Node Visited	Left Result	Right Result	Return Value	Tree State (Visual)
1	Start at root	3	?	?	?	3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
2	Check if root is p or q or null	3	?	?	?	Same as above
3	Recurse left subtree	5	?	?	?	Subtree rooted at 5
4	Check if node 5 is p or q or null	5	?	?	?	Subtree rooted at 5
5	Recurse left subtree	6	None	None	None	Leaf node 6
6	Recurse right subtree	2	?	?	?	Subtree rooted at 2
7	Check if node 2 is p or q or null	2	?	?	?	Subtree rooted at 2
8	Recurse left subtree	7	None	None	None	Leaf node 7
9	Recurse right subtree	4	None	None	None	Leaf node 4
10	Left and right both non-null at node 2	2	Node 7	Node 4	Node 2	Subtree rooted at 2
11	Return left result Node 2 to node 5	5	None	Node 2	Node 2	Subtree rooted at 5
12	Recurse right subtree	1	None	None	None	Subtree rooted at 1
13	Check if node 1 is p or q or null	1	?	?	?	Subtree rooted at 1
14	Recurse left subtree	0	None	None	None	Leaf node 0
15	Recurse right subtree	8	None	None	None	Leaf node 8
16	Left and right both null at node 1	1	None	None	None	Subtree rooted at 1
17	Left is Node 2, right is None at root 3	3	Node 2	None	Node 2	Full tree
18	Left and right both non-null at root 3	3	Node 2	Node 1	Node 3	Full tree
19	Return root 3 as LCA	3	Node 2	Node 1	Node 3	Full tree

💡 Recursion ends when nodes p=5 and q=1 are found and their lowest common ancestor is identified as node 3.

Variable Tracker

Variable	Start	After Step 5	After Step 10	After Step 16	After Step 19
root	3	2	2	1	3
left	?	None	Node 2	None	Node 2
right	?	Node 2	None	None	Node 1
Return Value	?	None	Node 2	None	Node 3

Key Moments - 3 Insights

Why do we return the root node when both left and right recursive calls are non-null?

Because it means p and q are found in different subtrees of this root, so this root is their lowest common ancestor (see execution_table rows 10, 18, 19).

What happens if the current node is either p or q?

We return the current node immediately (see execution_table row 4), because a node can be ancestor of itself.

Why do we return left.or(right) at the end?

Because if only one side returns a non-null node, that means both p and q are in that subtree, so we propagate that node up (see execution_table rows 11, 17).

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value at step 10 when visiting node 2?

A Node 2

B Node 7

C Node 4

D None

💡 Hint

Check the 'Return Value' column at step 10 in execution_table.

At which step does the recursion return None for both left and right subtrees?

A Step 5

B Step 16

C Step 14

D Step 18

💡 Hint

Look for step where both 'Left Result' and 'Right Result' are None in execution_table.

If node p was 7 instead of 5, how would the return value at step 19 change?

A It would still be node 3

B It would be node 2

C It would be node 5

D It would be None

💡 Hint

Consider the subtree containing nodes 7 and 1 and their lowest common ancestor from the tree structure.

Concept Snapshot

Lowest Common Ancestor (LCA) in Binary Tree:
- Start at root node
- If root is null or matches p or q, return root
- Recurse left and right subtrees
- If both sides return non-null, root is LCA
- Else return the non-null side
- Recursion finds nodes bottom-up
- Useful for ancestor queries in trees

Full Transcript

The Lowest Common Ancestor algorithm starts at the root of the binary tree. It checks if the current node is null or matches one of the target nodes p or q. If yes, it returns that node. Otherwise, it recursively searches the left and right subtrees. If both 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 node, it propagates that node upwards. This process continues until the LCA is found or the recursion ends. The execution table traces each step, showing which nodes are visited, what the recursive calls return, and how the final LCA is determined. Key moments clarify why returning the root when both sides are non-null is correct, why returning immediately when the node matches p or q is important, and why returning the non-null child propagates the found node. The visual quiz tests understanding of these steps and the final result. This method efficiently finds the LCA in a binary tree by exploring subtrees recursively and combining results.

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 node that appears first in an inorder traversal

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 (a node can be a descendant of itself).

2. Step 2: Identify the correct description

   Among the options, only the deepest common ancestor matches this definition.

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 lowest node connecting both nodes [OK]

Common Mistakes:

• Confusing LCA with the root node
• Choosing node based on value instead of position
• Selecting node based on traversal order

2. Which Rust function signature correctly represents a function to find the LCA in a binary tree where nodes are references with optional children?

easy

A. fn lowest_common_ancestor(root: &Option, p: &TreeNode, q: &TreeNode) -> Option<&TreeNode>

B. fn lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode

C. fn lowest_common_ancestor(root: &TreeNode, p: &TreeNode, q: &TreeNode) -> TreeNode

D. fn lowest_common_ancestor(root: &mut TreeNode, p: TreeNode, q: TreeNode) -> Option<TreeNode>

Solution

1. Step 1: Analyze the function parameters and return type

   The root is an optional boxed node reference because the tree can be empty. The nodes p and q are references to TreeNode. The return type is an optional reference to TreeNode because LCA might not exist.

2. Step 2: Match the correct signature

   fn lowest_common_ancestor(root: &Option, p: &TreeNode, q: &TreeNode) -> Option<&TreeNode> matches this pattern exactly with references and Option types.

3. Final Answer:

   fn lowest_common_ancestor(root: &Option, p: &TreeNode, q: &TreeNode) -> Option<&TreeNode> -> Option A

4. Quick Check:

   Correct Rust signature uses references and Option<Box> [OK]

Hint: Use &Option for root and return Option<&TreeNode> [OK]

Common Mistakes:

• Passing TreeNode by value instead of reference
• Returning owned TreeNode instead of reference
• Using mutable references unnecessarily

3. Given the following Rust code snippet for LCA, what will be the output if nodes p=5 and q=1 are searched in the tree?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

// Tree structure:
//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8

// Calling lowest_common_ancestor(root, &p, &q) returns node with value:
let lca = lowest_common_ancestor(&root, &p, &q);
println!("{}", lca.unwrap().val);

medium

A. 5

B. 3

C. 1

D. 2

Solution

1. Step 1: Visualize the tree and nodes p and q

   Node p=5 is left child of root 3, node q=1 is right child of root 3.

2. Step 2: Find the lowest common ancestor

   The lowest node that has both 5 and 1 as descendants is the root node 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: LCA of nodes on different sides is their root ancestor [OK]

Common Mistakes:

• Choosing one of the nodes instead of their ancestor
• Confusing child nodes as LCA
• Ignoring tree structure

4. Identify the bug in this Rust function snippet for finding LCA:

fn lowest_common_ancestor(root: &Option, p: &TreeNode, q: &TreeNode) -> Option<&TreeNode> {
    if root.is_none() { return None; }
    let node = root.as_ref().unwrap();
    if node.val == p.val || node.val == q.val {
        return Some(node);
    }
    let left = lowest_common_ancestor(&node.left, p, q);
    let right = lowest_common_ancestor(&node.right, p, q);
    if left.is_some() && right.is_some() {
        return Some(node);
    }
    if left.is_some() {
        return left;
    }
    right;
}

medium

A. Missing return statement in last line

B. Incorrect use of unwrap causing panic

C. Function returns owned TreeNode instead of reference

D. Function does not handle None cases properly

Solution

1. Step 1: Trace the control flow paths

   The function handles empty root, current node matching p/q, and both subtrees containing descendants.

2. Step 2: Analyze the final path

   When neither both-some nor left-some conditions trigger (left None), it reaches right;. The semicolon turns it into a statement that evaluates right but discards it, ending the function without returning a value. Thus, missing return statement.

3. Final Answer:

   Missing return statement in last line -> Option A

4. Quick Check:

   right; discards result instead of returning [OK]

Hint: Semicolon on last expression prevents implicit return [OK]

Common Mistakes:

• Adding semicolon to last line discarding result
• Thinking unwrap causes panic without checking is_none
• Confusing ownership with references

5. You have a binary tree where nodes can have duplicate values. How would you modify the LCA function in Rust to correctly find the LCA of two nodes given their references (not values)?

hard

A. Return the first node found with matching value as LCA

B. Use node values for comparison as usual, duplicates won't affect result

C. Convert tree to a binary search tree first to avoid duplicates

D. Compare nodes by their memory addresses or references instead of values

Solution

1. Step 1: Understand the problem with duplicates

   When nodes have duplicate values, comparing by value is ambiguous and can return wrong LCA.

2. Step 2: Use node references for comparison

   Comparing nodes by their memory addresses or references ensures exact node identity, avoiding confusion from duplicates.

3. Step 3: Choose the correct approach

   Compare nodes by their memory addresses or references instead of values correctly suggests comparing nodes by references, which is the safe and correct method in Rust.

4. Final Answer:

   Compare nodes by their memory addresses or references instead of values -> Option D

5. Quick Check:

   Use references, not values, to handle duplicates [OK]

Hint: Use node references, not values, to handle duplicates [OK]

Common Mistakes:

• Comparing nodes by value causing wrong LCA
• Trying to convert tree to BST unnecessarily
• Returning first matching value node ignoring duplicates