Lowest Common Ancestor in Binary Tree in DSA Rust - Build from Scratch

Lowest Common Ancestor in Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to find the closest common ancestor of two family members.

🎯 Goal: Build a Rust program that creates a binary tree, sets two target nodes, and finds their lowest common ancestor (LCA).

📋 What You'll Learn

Create a binary tree with nodes having integer values

Define two target nodes to find their LCA

Implement a function to find the LCA of the two nodes

Print the value of the LCA node

💡 Why This Matters

🌍 Real World

Finding the lowest common ancestor is useful in family trees, organizational charts, and file directory structures to find shared ancestors or common points.

💼 Career

Understanding tree traversal and recursive algorithms is important for software engineers working with hierarchical data, databases, and system design.

1

Create the Binary Tree Structure

Define a TreeNode struct with val as i32, and optional left and right children as Box<TreeNode>. Then create a binary tree with root value 3, left child 5, and right child 1.

DSA Rust

// Define TreeNode struct and create root node with left and right children
// Your code here

Hint

Use Option<Box<TreeNode>> for left and right children to allow empty nodes.

2

Set Target Nodes to Find LCA

Inside main, create two variables p and q that refer to the left child node with value 5 and the right child node with value 1 of the root, respectively.

DSA Rust

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

fn main() {
    let root = TreeNode {
        val: 3,
        left: Some(Box::new(TreeNode {
            val: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 1,
            left: None,
            right: None,
        })),
    };
    // Create variables p and q referring to nodes with values 5 and 1
    // Your code here
}

Hint

Use as_ref().unwrap() to get references to the child nodes inside Option.

3

Implement the Lowest Common Ancestor Function

Write a recursive function lowest_common_ancestor that takes references to root, p, and q of type &TreeNode and returns an Option<&TreeNode>. The function should return the lowest common ancestor node of p and q in the binary tree rooted at root.

DSA Rust

fn lowest_common_ancestor(root: &'a TreeNode, p: &'a TreeNode, q: &'a TreeNode) -> Option {
    if root.val == p.val || root.val == q.val {
        return Some(root);
    }
    let left = match &root.left {
        Some(left_node) => lowest_common_ancestor(left_node, p, q),
        None => None,
    let right = match &root.right {
        Some(right_node) => lowest_common_ancestor(right_node, p, q),
        None => None,
    if left.is_some() && right.is_some() {
        return Some(root);
    }
    if left.is_some() {
        return left;
    }
    right

Hint

Check if the current node matches p or q. Recursively search left and right subtrees. If both sides return a node, current node is LCA.

4

Print the Lowest Common Ancestor Value

Call lowest_common_ancestor with root, p, and q and print the val of the returned node using println!. The output should be the integer value of the LCA node.

DSA Rust

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

fn lowest_common_ancestor(root: &'a TreeNode, p: &'a TreeNode, q: &'a TreeNode) -> Option {
    if root.val == p.val || root.val == q.val {
        return Some(root);
    }

    let left = match &root.left {
        Some(left_node) => lowest_common_ancestor(left_node, p, q),
        None => None,
    };

    let right = match &root.right {
        Some(right_node) => lowest_common_ancestor(right_node, p, q),
        None => None,
    };

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

    if left.is_some() {
        return left;
    }

    right
}

fn main() {
    let root = TreeNode {
        val: 3,
        left: Some(Box::new(TreeNode {
            val: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 1,
            left: None,
            right: None,
        })),
    };
    let p = root.left.as_ref().unwrap();
    let q = root.right.as_ref().unwrap();

    // Call lowest_common_ancestor and print the val of the result
    // Your code here
}

Hint

Call lowest_common_ancestor with references and unwrap the result to print the val.

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