BST Find Maximum Element in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the maximum element in a BST

What is the output of this Rust code that finds the maximum element in a binary search tree?

DSA Rust

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn find_max(&self) -> i32 {
        match &self.right {
            Some(right_node) => right_node.find_max(),
            None => self.value,
        }
    }
}

fn main() {
    let tree = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 20,
            left: None,
            right: Some(Box::new(Node {
                value: 30,
                left: None,
                right: None,
            })),
        })),
    };
    println!("{}", tree.find_max());
}

A 10

B 20

C 30

D 5

💡 Hint

Remember, in a BST, the maximum element is the rightmost node.

The find_max function recursively goes to the right child until it finds a node with no right child. That node's value is the maximum. Here, the rightmost node has value 30.

❓ Predict Output

intermediate

Output of find_max on a single-node BST

What will be printed when find_max is called on a BST with only one node?

DSA Rust

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn find_max(&self) -> i32 {
        match &self.right {
            Some(right_node) => right_node.find_max(),
            None => self.value,
        }
    }
}

fn main() {
    let tree = Node {
        value: 42,
        left: None,
        right: None,
    };
    println!("{}", tree.find_max());
}

A 42

B 0

C None

D Error

💡 Hint

If there is no right child, the current node's value is the maximum.

Since the tree has only one node with value 42 and no right child, find_max returns 42.

🔧 Debug

advanced

Identify the error in this BST maximum finder

What error will this Rust code produce when trying to find the maximum element in a BST?

DSA Rust

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn find_max(&self) -> i32 {
        if self.right.is_some() {
            self.right.as_ref().unwrap().find_max()
        } else {
            self.value
        }
    }
}

fn main() {
    let tree = Node {
        value: 15,
        left: None,
        right: None,
    };
    println!("{}", tree.find_max());
}

A panic at unwrap on None value

B compilation error: cannot move out of borrowed content

C prints 0

D compiles and prints 15

💡 Hint

Check how unwrap() is used on a reference to Option.

Calling unwrap() on &Option> tries to move the Box out of a borrowed reference, which Rust forbids. This causes a compilation error.

🧠 Conceptual

advanced

Why does find_max only check the right subtree in a BST?

In a binary search tree, why is it sufficient to only follow the right child nodes to find the maximum element?

A Because all values in the right subtree are greater than the current node's value

B Because the left subtree contains the maximum value

C Because the tree is balanced and maximum is always at the root

D Because the maximum value is always stored in the leftmost node

💡 Hint

Recall the BST property about node values in left and right subtrees.

In a BST, all values in the right subtree are greater than the current node's value, so the maximum must be in the right subtree or the current node if no right child exists.

🚀 Application

expert

Find maximum element after inserting nodes in BST

Given the following sequence of insertions into an empty BST: 25, 15, 50, 10, 22, 35, 70, what is the maximum element in the BST?

A 50

B 25

C 35

D 70

💡 Hint

The maximum element is the rightmost node after all insertions.

After inserting all nodes, the rightmost node is 70, which is the maximum element in the BST.

Practice

1. In a Binary Search Tree (BST), where is the maximum element always located?

easy

A. At any leaf node

B. At the leftmost node

C. At the rightmost node

D. At the root node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Locate maximum element

   The maximum element is the rightmost node because it has no larger right child.

3. Final Answer:

   At the rightmost node -> Option C

4. Quick Check:

   Maximum = rightmost node [OK]

Hint: Maximum is always the rightmost node in BST [OK]

Common Mistakes:

• Confusing maximum with root node
• Thinking maximum is at leftmost node
• Assuming maximum can be any leaf

2. Which Rust code snippet correctly finds the maximum element in a BST node structure?

easy

A. fn find_max(node: &Option) -> i32 { let mut current = node; while let Some(ref n) = current { if n.right.is_none() { return n.value; } current = &n.right; } unreachable!() }

B. fn find_max(node: &Option) -> i32 { node.unwrap().value }

C. fn find_max(node: &Option) -> i32 { node.as_ref().unwrap().left.unwrap().value }

D. fn find_max(node: &Option) -> i32 { 0 }

Solution

1. Step 1: Analyze code logic

   fn find_max(node: &Option) -> i32 { let mut current = node; while let Some(ref n) = current { if n.right.is_none() { return n.value; } current = &n.right; } unreachable!() } uses a loop to traverse right children until none remain, returning the rightmost node's value.

2. Step 2: Check other options

   fn find_max(node: &Option) -> i32 { node.unwrap().value } returns root value only, C returns left child value, D returns constant 0, all incorrect.

3. Final Answer:

   Iterative right traversal to rightmost node -> Option A

4. Quick Check:

   Traverse right until None = max value [OK]

Hint: Traverse right child until None to find max [OK]

Common Mistakes:

• Returning root value without traversal
• Accessing left child instead of right
• Returning a fixed value ignoring tree

3. What is the output of this Rust code that finds the maximum element in a BST?

struct Node { value: i32, left: Option, right: Option }

fn find_max(node: &Option) -> i32 {
    let mut current = node;
    while let Some(ref n) = current {
        if n.right.is_none() {
            return n.value;
        }
        current = &n.right;
    }
    unreachable!()
}

fn main() {
    let tree = Some(Box::new(Node {
        value: 10,
        left: Some(Box::new(Node { value: 5, left: None, right: None })),
        right: Some(Box::new(Node {
            value: 15,
            left: None,
            right: Some(Box::new(Node { value: 20, left: None, right: None }))
        }))
    }));
    println!("{}", find_max(&tree));
}

medium

A. 10

B. 20

C. 15

D. 5

Solution

1. Step 1: Trace the tree structure

   Root is 10, right child 15, right child's right child 20 (rightmost node).

2. Step 2: Follow find_max logic

   Function moves right until no right child: stops at node with value 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   Rightmost node value = 20 [OK]

Hint: Rightmost node value is maximum [OK]

Common Mistakes:

• Returning root value instead of rightmost
• Confusing left and right children
• Not following loop to last right node

4. Identify the bug in this Rust function that tries to find the maximum element in a BST:

fn find_max(node: &Option) -> i32 {
    if node.is_none() {
        return 0;
    }
    let mut current = node;
    while current.is_some() {
        if current.as_ref().unwrap().right.is_none() {
            return current.as_ref().unwrap().value;
        }
        current = ¤t.as_ref().unwrap().left;
    }
    0
}

medium

A. It unwraps without checking None

B. It returns 0 for empty tree instead of error

C. It uses a loop instead of recursion

D. It traverses left child instead of right child

Solution

1. Step 1: Analyze traversal direction

   Function moves to left child in loop, but max is in right subtree.

2. Step 2: Identify correct traversal

   To find max, must traverse right child until None, not left.

3. Final Answer:

   It traverses left child instead of right child -> Option D

4. Quick Check:

   Max = rightmost node, not left [OK]

Hint: Max element is rightmost, so traverse right [OK]

Common Mistakes:

• Going left instead of right
• Returning 0 silently for empty tree
• Unwrapping without safe checks

5. Given a BST where some nodes have duplicate maximum values on the right subtree, how would you modify the Rust function to return the maximum value correctly?

hard

A. Traverse right until None and return the last node's value

B. Use recursion to check the left subtree and return max value

C. Traverse right and left children to find max value manually

D. Return the root value as maximum if duplicates exist

Solution

1. Step 1: Understand duplicates in BST

   In a BST (allowing duplicates typically on right), the maximum value(s) propagate to the rightmost node.

2. Step 2: Correct approach

   Traverse right until None; this reaches the rightmost node holding the maximum value, even with duplicates.

3. Final Answer:

   Traverse right until None and return the last node's value -> Option A

4. Quick Check:

   Rightmost = max even with duplicates [OK]

Hint: Right traversal finds max even with duplicates [OK]

Common Mistakes:

• Using recursion on left subtree
• Traversing both subtrees unnecessarily
• Returning root value with duplicates