Lowest Common Ancestor in Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCA function for given nodes

What is the output of the Rust function that finds the Lowest Common Ancestor (LCA) of nodes 5 and 1 in the given binary tree?

DSA Rust

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

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

fn lowest_common_ancestor(root: Option<Rc<RefCell<TreeNode>>>, p: i32, q: i32) -> Option<i32> {
    fn helper(node: &Option<Rc<RefCell<TreeNode>>>, p: i32, q: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(n) = node {
            let n_borrow = n.borrow();
            if n_borrow.val == p || n_borrow.val == q {
                return Some(Rc::clone(n));
            }
            let left = helper(&n_borrow.left, p, q);
            let right = helper(&n_borrow.right, p, q);
            if left.is_some() && right.is_some() {
                return Some(Rc::clone(n));
            }
            if left.is_some() {
                return left;
            }
            right
        } else {
            None
        }
    }

    helper(&root, p, q).map(|node| node.borrow().val)
}

fn main() {
    let node5 = Rc::new(RefCell::new(TreeNode { val: 5, left: None, right: None }));
    let node1 = Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None }));
    let node6 = Rc::new(RefCell::new(TreeNode { val: 6, left: None, right: None }));
    let node2 = Rc::new(RefCell::new(TreeNode { val: 2, left: None, right: None }));
    let node0 = Rc::new(RefCell::new(TreeNode { val: 0, left: None, right: None }));
    let node8 = Rc::new(RefCell::new(TreeNode { val: 8, left: None, right: None }));
    let node7 = Rc::new(RefCell::new(TreeNode { val: 7, left: None, right: None }));
    let node4 = Rc::new(RefCell::new(TreeNode { val: 4, left: None, right: None }));

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

    let root = Some(Rc::clone(&node5));

    let lca = lowest_common_ancestor(root, 5, 1);
    println!("{}", lca.unwrap());
}

A 1

B 5

C 2

D None

💡 Hint

The LCA of a node with itself or its ancestor is the ancestor node.

The nodes 5 and 1 have 5 as their lowest common ancestor because 5 is the root and ancestor of 1.

❓ Predict Output

intermediate

Output of LCA function for nodes 7 and 4

What is the output of the Rust LCA function when finding the lowest common ancestor of nodes 7 and 4 in the same binary tree?

DSA Rust

/* Same tree setup as previous challenge */

fn main() {
    // Tree nodes and structure as before
    let node5 = Rc::new(RefCell::new(TreeNode { val: 5, left: None, right: None }));
    let node1 = Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None }));
    let node6 = Rc::new(RefCell::new(TreeNode { val: 6, left: None, right: None }));
    let node2 = Rc::new(RefCell::new(TreeNode { val: 2, left: None, right: None }));
    let node0 = Rc::new(RefCell::new(TreeNode { val: 0, left: None, right: None }));
    let node8 = Rc::new(RefCell::new(TreeNode { val: 8, left: None, right: None }));
    let node7 = Rc::new(RefCell::new(TreeNode { val: 7, left: None, right: None }));
    let node4 = Rc::new(RefCell::new(TreeNode { val: 4, left: None, right: None }));

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

    let root = Some(Rc::clone(&node5));

    let lca = lowest_common_ancestor(root, 7, 4);
    println!("{}", lca.unwrap());
}

A 2

B 4

C 7

D 5

💡 Hint

Both nodes 7 and 4 are children of node 2.

The lowest common ancestor of nodes 7 and 4 is node 2 because both are direct children of node 2.

🔧 Debug

advanced

Identify the error in LCA function implementation

Which option describes the error in this Rust LCA function implementation that causes it to fail when both nodes are on the same subtree?

DSA Rust

fn lowest_common_ancestor(root: Option<Rc<RefCell<TreeNode>>>, p: i32, q: i32) -> Option<i32> {
    fn helper(node: &Option<Rc<RefCell<TreeNode>>>, p: i32, q: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(n) = node {
            let n_borrow = n.borrow();
            if n_borrow.val == p || n_borrow.val == q {
                return Some(Rc::clone(n));
            }
            let left = helper(&n_borrow.left, p, q);
            let right = helper(&n_borrow.right, p, q);
            if left.is_some() && right.is_some() {
                return Some(Rc::clone(n));
            }
            if left.is_some() {
                return left;
            }
            if right.is_some() {
                return right;
            }
            None
        } else {
            None
        }
    }

    helper(&root, p, q).map(|node| node.borrow().val)
}

A The function does not handle the case when both nodes are the same node.

B The function returns the root node always regardless of input.

C The function does not check if the current node is None before borrowing.

D The function incorrectly returns None when both nodes are in the left subtree only.

💡 Hint

Check the return logic when only one subtree returns a node.

When both nodes are in the same subtree, the function should return that subtree's result, but if the logic is incorrect, it might return None.

🧠 Conceptual

advanced

Understanding LCA properties in binary trees

Which statement about the Lowest Common Ancestor (LCA) in a binary tree is true?

A The LCA must be the root of the tree.

B The LCA of two nodes is always one of the nodes themselves.

C The LCA is the deepest node that has both nodes as descendants (where a node can be a descendant of itself).

D The LCA is always the parent of one of the nodes.

💡 Hint

Think about the definition of ancestor and descendant including the node itself.

By definition, the LCA is the deepest node that has both nodes as descendants, and a node can be a descendant of itself.

🚀 Application

expert

Number of nodes in subtree rooted at LCA

Given a binary tree and two nodes p and q, after finding their Lowest Common Ancestor (LCA), how many nodes are in the subtree rooted at the LCA if the subtree includes the LCA node itself?

DSA Rust

/* Assume the same tree as previous examples */

// Function to count nodes in subtree
fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if let Some(node) = root {
        let n = node.borrow();
        1 + count_nodes(n.left.clone()) + count_nodes(n.right.clone())
    } else {
        0
    }
}

fn main() {
    // Tree setup as before
    let node5 = Rc::new(RefCell::new(TreeNode { val: 5, left: None, right: None }));
    let node1 = Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None }));
    let node6 = Rc::new(RefCell::new(TreeNode { val: 6, left: None, right: None }));
    let node2 = Rc::new(RefCell::new(TreeNode { val: 2, left: None, right: None }));
    let node0 = Rc::new(RefCell::new(TreeNode { val: 0, left: None, right: None }));
    let node8 = Rc::new(RefCell::new(TreeNode { val: 8, left: None, right: None }));
    let node7 = Rc::new(RefCell::new(TreeNode { val: 7, left: None, right: None }));
    let node4 = Rc::new(RefCell::new(TreeNode { val: 4, left: None, right: None }));

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

    let root = Some(Rc::clone(&node5));

    let lca_node_val = lowest_common_ancestor(root.clone(), 7, 4).unwrap();

    // Find the LCA node reference
    fn find_node(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root {
            if node.borrow().val == val {
                return Some(Rc::clone(&node));
            }
            let left = find_node(node.borrow().left.clone(), val);
            if left.is_some() {
                return left;
            }
            find_node(node.borrow().right.clone(), val)
        } else {
            None
        }
    }

    let lca_node = find_node(root, lca_node_val);
    let count = count_nodes(lca_node);
    println!("{}", count);
}

A 3

B 5

C 4

D 6

💡 Hint

Count all nodes under node 2 including itself.

The subtree rooted at node 2 includes nodes 2, 7, and 4. Nodes 7 and 4 have no children, so total nodes are 3.

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