BST Find Maximum Element in DSA Rust

Mental Model

In a binary search tree, the biggest number is always the rightmost node. We keep going right until there is no more right child.

Analogy: Imagine walking down a street where houses get bigger as you go right. The biggest house is the last one on the right side with no more houses after it.

    10
   /  \
  5    15
       /  \
      12   20
             
Rightmost node is 20 -> the maximum element.

Dry Run Walkthrough

Input: BST: 10 -> 5, 15 -> 12, 20; find maximum element

Goal: Find the largest value in the BST by moving right until no more right child.

Step 1: Start at root node 10

10 -> [curr->15] -> 20
 /
5  15 -> 12, 20

Why: We start at root and move right because bigger values are on the right.

Step 2: Move curr pointer from 10 to 15

10 -> 15 -> [curr->20]
 /
5  15 -> 12, 20

Why: 15 is right child of 10, so we move right to find bigger values.

Step 3: Move curr pointer from 15 to 20

10 -> 15 -> 20 -> [curr->null]
 /
5  15 -> 12, 20

Why: 20 is right child of 15, move right again to find bigger value.

Step 4: No right child of 20, stop and return 20

10 -> 15 -> 20 -> null
 /
5  15 -> 12, 20

Why: No more right nodes means 20 is the maximum element.

Result:

Maximum element found: 20

Annotated Code

DSA Rust

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

#[derive(Debug)]
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 find_max(root: Option<Rc<RefCell<TreeNode>>>) -> Option<i32> {
    let mut curr = root;
    // advance curr to the rightmost node
    while let Some(node) = curr.clone() {
        if node.borrow().right.is_some() {
            curr = node.borrow().right.clone();
        } else {
            return Some(node.borrow().val);
        }
    }
    None
}

fn main() {
    // Construct BST:
    //       10
    //      /  \
    //     5    15
    //         /  \
    //        12   20
    let root = TreeNode::new(10);
    let node5 = TreeNode::new(5);
    let node15 = TreeNode::new(15);
    let node12 = TreeNode::new(12);
    let node20 = TreeNode::new(20);

    root.borrow_mut().left = Some(node5);
    root.borrow_mut().right = Some(node15.clone());
    node15.borrow_mut().left = Some(node12);
    node15.borrow_mut().right = Some(node20);

    if let Some(max_val) = find_max(Some(root)) {
        println!("Maximum element found: {}", max_val);
    } else {
        println!("Tree is empty");
    }
}

while let Some(node) = curr.clone() {

loop to traverse nodes while current node exists

if node.borrow().right.is_some() {

check if right child exists to move right

curr = node.borrow().right.clone();

advance curr to right child to find bigger values

return Some(node.borrow().val);

no right child means current node is max, return its value

Output

Maximum element found: 20

Complexity Analysis

Time: O(h) because we only move down the right children where h is the height of the tree

Space: O(1) because we use only a few pointers and no extra data structures

vs Alternative: Compared to traversing the whole tree (O(n)), this is faster because BST property lets us skip left subtrees.

Edge Cases

Empty tree (root is None)

Returns None indicating no maximum element

DSA Rust

while let Some(node) = curr.clone() {

Tree with only one node

Returns that node's value as maximum

DSA Rust

if node.borrow().right.is_some() {

Tree where all nodes only have left children

Returns root value as maximum since no right children exist

DSA Rust

if node.borrow().right.is_some() {

When to Use This Pattern

When you need the largest value in a BST, look for the rightmost node because BSTs keep bigger values on the right.

Common Mistakes

Mistake: Trying to traverse both left and right subtrees to find max
Fix: Only move right because max is always in the rightmost path

Mistake: Not handling empty tree and returning a value anyway
Fix: Check if root is None and return None before traversal

Summary

Finds the maximum element by moving right until no more right child exists.

Use when you want the largest value in a binary search tree quickly.

The key insight is that the maximum is always the rightmost node in a 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