Lowest Common Ancestor in Binary Tree in DSA Rust

Mental Model

Find the closest shared parent node of two given nodes in a tree by exploring paths from the root.

Analogy: Imagine a family tree where you want to find the closest common grandparent of two cousins by tracing their parents upwards until they meet.

      3
     / \
    5   1
   / \ / \
  6  2 0  8
    / \
   7   4

Here, 5 and 1 share 3 as their lowest common ancestor.

Dry Run Walkthrough

Input: Binary tree as above, find LCA of nodes 5 and 1

Goal: Find the lowest common ancestor node of 5 and 1, which is 3

Step 1: Start at root node 3, check if it matches 5 or 1

3 ↑
/ \
5  1
...

Why: We start from the root to explore both sides for the target nodes

Step 2: Recurse left subtree from node 5, check if it matches 5 or 1

5 ↑
/ \
6  2
...

Why: We search left subtree for nodes 5 or 1

Step 3: Node 5 matches one target, return node 5 up

Return 5

Why: Found one target node, propagate it upwards

Step 4: Recurse right subtree from node 1, check if it matches 5 or 1

1 ↑
/ \
0  8

Why: Search right subtree for nodes 5 or 1

Step 5: Node 1 matches the other target, return node 1 up

Return 1

Why: Found second target node, propagate it upwards

Step 6: At root 3, left returned 5 and right returned 1, so 3 is LCA

Return 3 as LCA

Why: Both targets found in different subtrees, root is their lowest common ancestor

Result:

3 -> left subtree: 5 -> ... , right subtree: 1 -> ...
Lowest Common Ancestor is node 3

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn lowest_common_ancestor(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: Rc<RefCell<TreeNode>>,
    q: Rc<RefCell<TreeNode>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return None;
    }
    let root_node = root.as_ref().unwrap();
    let root_val = root_node.borrow().val;
    if root_val == p.borrow().val || root_val == q.borrow().val {
        return root;
    }

    let left = lowest_common_ancestor(root_node.borrow().left.clone(), p.clone(), q.clone());
    let right = lowest_common_ancestor(root_node.borrow().right.clone(), p.clone(), q.clone());

    if left.is_some() && right.is_some() {
        return root;
    }
    if left.is_some() {
        return left;
    }
    right
}

fn main() {
    // Build the tree
    let root = TreeNode::new(3);
    let node5 = TreeNode::new(5);
    let node1 = TreeNode::new(1);
    let node6 = TreeNode::new(6);
    let node2 = TreeNode::new(2);
    let node0 = TreeNode::new(0);
    let node8 = TreeNode::new(8);
    let node7 = TreeNode::new(7);
    let node4 = TreeNode::new(4);

    root.borrow_mut().left = Some(node5.clone());
    root.borrow_mut().right = Some(node1.clone());
    node5.borrow_mut().left = Some(node6.clone());
    node5.borrow_mut().right = Some(node2.clone());
    node1.borrow_mut().left = Some(node0.clone());
    node1.borrow_mut().right = Some(node8.clone());
    node2.borrow_mut().left = Some(node7.clone());
    node2.borrow_mut().right = Some(node4.clone());

    let lca = lowest_common_ancestor(Some(root.clone()), node5.clone(), node1.clone());
    if let Some(lca_node) = lca {
        println!("Lowest Common Ancestor is node {}", lca_node.borrow().val);
    } else {
        println!("Lowest Common Ancestor not found");
    }
}

if root.is_none() { return None; }

handle empty subtree base case

if root_val == p.borrow().val || root_val == q.borrow().val { return root; }

if current node matches one target, return it

let left = lowest_common_ancestor(root_node.borrow().left.clone(), p.clone(), q.clone());

recurse left subtree to find targets

let right = lowest_common_ancestor(root_node.borrow().right.clone(), p.clone(), q.clone());

recurse right subtree to find targets

if left.is_some() && right.is_some() { return root; }

if targets found in both subtrees, current node is LCA

if left.is_some() { return left; }

if only left subtree has target(s), propagate left result

right

otherwise propagate right subtree result

Output

Lowest Common Ancestor is node 3

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing paths for both nodes and then comparing, this approach uses less space and is simpler

Edge Cases

Empty tree

Returns None immediately

DSA Rust

if root.is_none() { return None; }

One node is ancestor of the other

Returns the ancestor node as LCA

DSA Rust

if root_val == p.borrow().val || root_val == q.borrow().val { return root; }

Both nodes are the same

Returns that node as LCA

DSA Rust

if root_val == p.borrow().val || root_val == q.borrow().val { return root; }

When to Use This Pattern

When asked to find the closest shared parent of two nodes in a tree, use the Lowest Common Ancestor pattern by exploring subtrees recursively.

Common Mistakes

Mistake: Returning immediately when one target is found without checking the other subtree
Fix: Always check both left and right subtrees before deciding LCA

Mistake: Not handling the base case of empty subtree
Fix: Add a check to return None if the current node is None

Summary

Finds the closest shared parent node of two given nodes in a binary tree.

Use when you need to find the common ancestor of two nodes efficiently without storing paths.

The key insight is that if one target is found in each subtree of a node, that node is their lowest common ancestor.

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