Lowest Common Ancestor in Binary Tree in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the TreeNode struct with optional left and right children.

DSA Rust

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

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: [1],
            right: None,
        }
    }
}

Drag options to blanks, or click blank then click option'

ASome(Box::new(TreeNode::new(val)))

BSome(TreeNode::new(val))

CNone

DBox::new(None)

Attempts:

3 left

💡 Hint

Common Mistakes

Using Some with a new node instead of None.

Trying to assign a value directly without wrapping in Option.

The left child is initially empty, so we use None to indicate no child.

2fill in blank

medium

Complete the code to check if the current node is None in the LCA function.

DSA Rust

fn lowest_common_ancestor(root: &Option<Box<TreeNode>>, p: i32, q: i32) -> Option<i32> {
    if [1] {
        return None;
    }
    // rest of the code
}

Drag options to blanks, or click blank then click option'

Aroot.is_none()

Broot.is_some()

Croot == None

Droot.is_empty()

Attempts:

3 left

💡 Hint

Common Mistakes

Using is_some() which checks for presence, not absence.

Using == None which is less idiomatic in Rust.

We check if the root is None using is_none() to stop recursion.

3fill in blank

hard

Fix the error in the recursive call to lowest_common_ancestor for the left subtree.

DSA Rust

let left = lowest_common_ancestor(&[1].left, p, q);

Drag options to blanks, or click blank then click option'

Aroot

Broot.as_ref()

Croot.unwrap()

Droot.as_ref().unwrap()

Attempts:

3 left

💡 Hint

Common Mistakes

Calling unwrap() directly on root which is an Option reference.

Using root without dereferencing.

We use as_ref() to get a reference to the boxed node, then unwrap() to access the inner TreeNode.

4fill in blank

hard

Fill both blanks to correctly compare the current node's value with p and q.

DSA Rust

let val = [1].val;
if val == [2] || val == q {
    return Some(val);
}

Drag options to blanks, or click blank then click option'

Aroot.as_ref().unwrap()

Bp

Croot.unwrap()

Dq

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.unwrap() directly without as_ref().

Mixing up p and q in comparisons.

We get the current node's value by unwrapping the reference, then compare it with p and q.

5fill in blank

hard

Fill all three blanks to return the correct lowest common ancestor based on left and right recursive results.

DSA Rust

if left.is_some() && right.is_some() {
    return Some([1]);
}
if left.is_some() {
    return [2];
}
return [3];

Drag options to blanks, or click blank then click option'

Aval

Bleft

Cright

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Returning root instead of val when both sides are Some.

Returning right when left is Some and right is None.

If both left and right are found, current node is LCA (val). Otherwise, return whichever side is Some.

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