BST Inorder Predecessor in DSA Rust - Build from Scratch

BST Inorder Predecessor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the inorder predecessor of a given node. The inorder predecessor is the node with the largest value smaller than the given node's value.Think of the BST as a family tree sorted by age, and you want to find the person who is just older than a specific person but younger than everyone else older than them.

🎯 Goal: Build a Rust program that creates a BST, sets up a target value, finds the inorder predecessor of that value in the BST, and prints the predecessor's value or None if it does not exist.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 10, 30, 5, 15, 25, 35

Create a variable called target with the value 15

Write a function inorder_predecessor that finds the inorder predecessor of target in the BST

Print the predecessor's value or None if no predecessor exists

💡 Why This Matters

🌍 Real World

Finding inorder predecessors is useful in database indexing and memory management where sorted data needs quick predecessor lookups.

💼 Career

Understanding BST traversal and predecessor/successor logic is important for software engineers working on search algorithms, databases, and system design.

1

Create the BST structure and nodes

Create a struct called Node with fields value: i32, left: Option>, and right: Option>. Then create a BST with the root node having value 20, left child 10, right child 30, and their respective children: 5, 15, 25, 35 as shown.

DSA Rust

// Define Node struct and create BST with nodes 20, 10, 30, 5, 15, 25, 35
// Your code here

Hint

Use Option> for left and right children to allow empty branches.

Build the tree from bottom up or top down as you prefer.

2

Set the target value to find predecessor for

Inside main, create a variable called target and set it to 15.

DSA Rust

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

fn main() {
    let root = Some(Box::new(Node {
        value: 20,
        left: 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: None,
            })),
        })),
        right: Some(Box::new(Node {
            value: 30,
            left: Some(Box::new(Node {
                value: 25,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 35,
                left: None,
                right: None,
            })),
        })),
    }));

    // Create a variable called target and set it to 15
    // Your code here
}

Hint

Just add let target = 15; inside main.

3

Write the function to find inorder predecessor

Write a function called inorder_predecessor that takes root: &Option> and target: i32 and returns Option. This function should find the inorder predecessor of target in the BST. Use a loop or recursion to traverse the tree. If the current node's value is less than target, update predecessor and go right. Otherwise, go left.

DSA Rust

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

fn inorder_predecessor(root: &Option>, target: i32) -> Option {
    // Implement the inorder predecessor logic here
    // Your code here
}

fn main() {
    let root = Some(Box::new(Node {
        value: 20,
        left: 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: None,
            })),
        })),
        right: Some(Box::new(Node {
            value: 30,
            left: Some(Box::new(Node {
                value: 25,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 35,
                left: None,
                right: None,
            })),
        })),
    }));

    let target = 15;

    // Call inorder_predecessor here
    // Your code here
}

Hint

Use a loop to move down the tree. If node's value is less than target, update predecessor and go right. Else go left.

4

Print the inorder predecessor result

In main, call inorder_predecessor with &root and target. Then print the result using println!("{:?}", pred); where pred is the returned value.

DSA Rust

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

fn inorder_predecessor(root: &Option>, target: i32) -> Option {
    let mut current = root;
    let mut predecessor = None;

    while let Some(node) = current {
        if node.value < target {
            predecessor = Some(node.value);
            current = &node.right;
        } else {
            current = &node.left;
        }
    }

    predecessor
}

fn main() {
    let root = Some(Box::new(Node {
        value: 20,
        left: 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: None,
            })),
        })),
        right: Some(Box::new(Node {
            value: 30,
            left: Some(Box::new(Node {
                value: 25,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 35,
                left: None,
                right: None,
            })),
        })),
    }));

    let target = 15;

    let pred = inorder_predecessor(&root, target);

    // Print the predecessor
    // Your code here
}

Hint

Use println!("{:?}", pred); to print the predecessor.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The node with the largest value smaller than the given node

B. The node with the smallest value larger than the given node

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand BST property

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node.

2. Step 2: Define inorder predecessor

   The inorder predecessor is the node visited just before the current node in an inorder traversal, which means it has the largest value smaller than the current node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option A

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Inorder predecessor is largest smaller node [OK]

Common Mistakes:

• Confusing predecessor with successor
• Choosing child nodes directly without checking values
• Thinking predecessor is always left child

2. Which Rust code snippet correctly finds the inorder predecessor of a node with a left subtree in a BST?

easy

A. let pred = node.right.clone();

B. let mut pred = node.right.as_ref(); while let Some(left) = pred.unwrap().left.as_ref() { pred = Some(left); }

C. let mut pred = node.left.as_ref(); while let Some(right) = pred.unwrap().right.as_ref() { pred = Some(right); }

D. let pred = node.left.clone();

Solution

1. Step 1: Identify left subtree traversal

   The inorder predecessor is the rightmost node in the left subtree, so start from node.left.

2. Step 2: Traverse to rightmost node

   Keep moving to the right child until no more right child exists to find the largest node in left subtree.

3. Final Answer:

   let mut pred = node.left.as_ref(); while let Some(right) = pred.unwrap().right.as_ref() { pred = Some(right); } -> Option C

4. Quick Check:

   Traverse left subtree rightmost node = let mut pred = node.left.as_ref(); while let Some(right) = pred.unwrap().right.as_ref() { pred = Some(right); } [OK]

Hint: Go left once, then right as far as possible [OK]

Common Mistakes:

• Starting from right subtree instead of left
• Not looping to the rightmost node
• Using clone instead of reference traversal

3. Given the BST below and node value 15, what is the inorder predecessor?

       20
      /  \
    10    30
      \     \
      15    40

medium

A. 30

B. 15

C. 20

D. 10

Solution

1. Step 1: Locate node 15 and its left subtree

   Node 15 has no left child, so we look for the ancestor smaller than 15.

2. Step 2: Find largest ancestor smaller than 15

   10 is the parent of 15 and smaller than 15, so 10 is the inorder predecessor.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Largest smaller ancestor = 10 [OK]

Hint: If no left child, go up to smaller ancestor [OK]

Common Mistakes:

• Choosing node itself as predecessor
• Choosing larger ancestor incorrectly
• Ignoring no left subtree case

4. Identify the bug in this Rust function to find the inorder predecessor of a BST node:

fn inorder_predecessor(node: &Option) -> Option<i32> {
    let mut current = node.as_ref()?.left.as_ref();
    while current?.right.is_some() {
        current = current?.right.as_ref();
    }
    current.map(|n| n.val)
}

medium

A. Using '?' operator on Option without handling None case

B. Starting from node.right instead of node.left

C. Returning node.val instead of predecessor value

D. Not checking if node has left child before traversal

Solution

1. Step 1: Analyze use of '?' operator in loop condition

   The '?' operator unwraps Option or returns None; using it inside while condition causes panic if None.

2. Step 2: Identify safe way to traverse Option references

   Must use pattern matching or if let to safely unwrap Options instead of '?' in loop condition.

3. Final Answer:

   Using '?' operator on Option without handling None case -> Option A

4. Quick Check:

   Unsafe '?' in loop condition causes panic [OK]

Hint: Avoid '?' in loop conditions on Option [OK]

Common Mistakes:

• Using '?' inside loops causing runtime panic
• Ignoring None cases in Option traversal
• Confusing left and right subtree

5. You want to find the inorder predecessor of a node in a BST that has no left child. Which approach correctly finds it?

hard

A. Return the rightmost node in the right subtree

B. Traverse up the tree to find the nearest ancestor whose right child is also an ancestor of the node

C. Return the leftmost node in the right subtree

D. Return the root node always

Solution

1. Step 1: Understand no left child case

   If node has no left child, predecessor is not in left subtree but among ancestors.

2. Step 2: Find nearest ancestor where node is in right subtree

   Traverse up until you find an ancestor whose right child is also an ancestor of the node; that ancestor is the predecessor.

3. Final Answer:

   Traverse up the tree to find the nearest ancestor whose right child is also an ancestor of the node -> Option B

4. Quick Check:

   No left child -> find right-side ancestor [OK]

Hint: Go up to ancestor where node is in right subtree [OK]

Common Mistakes:

• Returning nodes from right subtree incorrectly
• Always returning root node
• Ignoring ancestor traversal