BST Inorder Predecessor in DSA Rust - Deep Dive

Overview - BST Inorder Predecessor

What is it?

A Binary Search Tree (BST) is a tree where each node has at most two children, and the left child's value is less than the parent, while the right child's value is greater. The inorder predecessor of a node in a BST is the node that comes immediately before it when the tree is traversed in sorted order (left-root-right). Finding the inorder predecessor helps in many tree operations like deletion or finding closest smaller values.

Why it matters

Without the concept of an inorder predecessor, operations like deleting a node with two children become complicated and inefficient. It helps maintain the BST properties during updates and queries. In real life, this is like knowing the previous item in a sorted list without sorting again, saving time and effort.

Where it fits

Before learning inorder predecessor, you should understand BST structure and inorder traversal. After mastering this, you can learn about inorder successor, tree deletion algorithms, and balanced BSTs like AVL or Red-Black trees.

Mental Model

Core Idea

The inorder predecessor of a node in a BST is the largest node smaller than that node, found by looking left once and then as far right as possible.

Think of it like...

Imagine a line of people sorted by height. To find the person just shorter than a given person, you look to the left (shorter side) and then find the tallest person there who is still shorter than your person.

          ┌─────────────┐
          │   Node X    │
          └──────┬──────┘
                 │
         ┌───────┴───────┐
         │   Left Child  │
         └───────┬───────┘
                 │
         ┌───────┴───────┐
         │ Rightmost Node│  ← This is the inorder predecessor
         └───────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding BST Structure

Concept: Learn what a Binary Search Tree is and how nodes are arranged.

A BST is a tree where each node has a value. Left child nodes have smaller values, right child nodes have larger values. This property helps in quick searching and sorting.

Result

You can quickly find if a value exists by comparing and moving left or right.

Understanding BST structure is essential because the inorder predecessor depends on the sorted order BST maintains.

2

Foundation

Inorder Traversal Basics

Concept: Learn how inorder traversal visits nodes in sorted order.

Inorder traversal visits left subtree, then current node, then right subtree recursively. This produces sorted values from a BST.

Result

Visiting nodes in ascending order: e.g., 1 -> 3 -> 5 -> 7 -> 9

Knowing inorder traversal order is key to understanding what 'predecessor' means in this context.

3

Intermediate

Defining Inorder Predecessor

🤔Before reading on: do you think the inorder predecessor is always the left child of a node? Commit to your answer.

Concept: The inorder predecessor is the node that comes immediately before the given node in inorder traversal.

If the node has a left child, the predecessor is the rightmost node in that left subtree. If no left child, predecessor is one of the ancestors where the node lies in the right subtree.

Result

You can find the predecessor by checking left subtree or moving up ancestors.

Understanding both cases prevents mistakes when searching for predecessors in different tree shapes.

4

Intermediate

Finding Predecessor with Left Subtree

🤔Before reading on: if a node has a left child, do you think the predecessor is the left child itself or deeper? Commit to your answer.

Concept: When left subtree exists, predecessor is the rightmost node in that subtree.

Start at left child, then keep moving right until no more right child exists. That node is the predecessor.

Result

Predecessor found by descending left once, then right as far as possible.

Knowing to go right inside left subtree ensures you find the closest smaller value, not just any smaller value.

5

Intermediate

Finding Predecessor Without Left Subtree

🤔Before reading on: if a node has no left child, do you think the predecessor is below or above it in the tree? Commit to your answer.

Concept: If no left child, predecessor is an ancestor where the node is in the right subtree.

Move up the tree until you find a node that is a right child of its parent. That parent is the predecessor.

Result

Predecessor found by moving up ancestors until a right turn is found.

Understanding ancestor traversal prevents missing predecessors when left subtree is absent.

6

Advanced

Implementing Inorder Predecessor in Rust

🤔Before reading on: do you think the implementation should handle both cases (left subtree and ancestor) separately or combined? Commit to your answer.

Concept: Implement a function that finds the inorder predecessor by checking left subtree first, then ancestors.

```rust use std::rc::Rc; use std::cell::RefCell; #[derive(Debug)] struct TreeNode { val: i32, left: Option>>, right: Option>>, } fn inorder_predecessor(root: Option>>, target: i32) -> Option { let mut predecessor = None; let mut current = root.clone(); while let Some(node_rc) = current { let node = node_rc.borrow(); if node.val < target { predecessor = Some(node.val); current = node.right.clone(); } else { current = node.left.clone(); } } predecessor } fn main() { // Build BST manually let node1 = Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None })); let node3 = Rc::new(RefCell::new(TreeNode { val: 3, left: None, right: None })); let node2 = Rc::new(RefCell::new(TreeNode { val: 2, left: Some(node1), right: Some(node3) })); let node5 = Rc::new(RefCell::new(TreeNode { val: 5, left: None, right: None })); let root = Rc::new(RefCell::new(TreeNode { val: 4, left: Some(node2), right: Some(node5) })); let pred = inorder_predecessor(Some(root), 4); println!("Inorder predecessor of 4 is: {:?}", pred); } ```

Result

Inorder predecessor of 4 is: Some(3)

Implementing with a loop that moves left or right based on comparison efficiently finds the predecessor without explicit recursion.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the inorder predecessor always exists for any node in a BST? Commit to your answer.

Concept: Explore cases where predecessor does not exist and optimize search for large trees.

The smallest node has no predecessor. The function returns None in this case. For large trees, iterative search avoids stack overflow and improves speed. Also, caching parent pointers can speed up ancestor traversal.

Result

Correctly returns None when no predecessor exists and performs efficiently on big trees.

Knowing edge cases and performance tricks is crucial for robust, production-ready BST operations.

Under the Hood

The BST property allows searching for predecessor by comparing values and moving left or right. Internally, the algorithm uses the tree's sorted structure to avoid full traversal. When a left subtree exists, the rightmost node there is the largest smaller value. Without a left subtree, the algorithm climbs ancestors to find a node where the current node lies in the right subtree, which is the predecessor.

Why designed this way?

BSTs are designed to keep data sorted for fast search. The inorder predecessor leverages this sorted order to find the closest smaller value efficiently. Alternatives like full inorder traversal are slower. This design balances simplicity and speed.

Root
 │
 ├── Left Subtree
 │    └── Rightmost Node (Predecessor if left subtree exists)
 └── Right Subtree

If no left subtree:
Current Node
  ↑
Ancestor where Current Node is in right subtree (Predecessor)

Myth Busters - 4 Common Misconceptions

Quick: Is the inorder predecessor always the left child of a node? Commit to yes or no.

Common Belief: The inorder predecessor is always the left child of the node.

Reality: The predecessor is the rightmost node in the left subtree, which may be deeper than the immediate left child.

Why it matters: Mistaking the left child as the predecessor can cause incorrect tree operations and bugs in deletion or traversal.

Quick: Does every node in a BST have an inorder predecessor? Commit to yes or no.

Common Belief: Every node has an inorder predecessor.

Reality: The smallest node in the BST has no inorder predecessor.

Why it matters: Assuming a predecessor always exists can cause null pointer errors or crashes.

Quick: When no left subtree exists, is the predecessor below or above the node? Commit to your answer.

Common Belief: If no left subtree, the predecessor is below the node somewhere.

Reality: If no left subtree, the predecessor is an ancestor above the node where the node is in the right subtree.

Why it matters: Failing to check ancestors leads to missing the predecessor and incorrect tree behavior.

Quick: Is recursive traversal always better than iterative for finding predecessor? Commit to yes or no.

Common Belief: Recursive traversal is always simpler and better.

Reality: Iterative traversal avoids stack overflow and is more efficient for large trees.

Why it matters: Using recursion blindly can cause performance issues and crashes in deep trees.

Expert Zone

1

In BSTs without parent pointers, finding the predecessor requires tracking ancestors during search, which can be optimized with extra memory.

2

Caching the rightmost node of left subtrees can speed up repeated predecessor queries in static trees.

3

In threaded BSTs, predecessor pointers are stored explicitly, allowing O(1) predecessor access without traversal.

When NOT to use

If the tree is not a BST or is unbalanced heavily, inorder predecessor search may be inefficient. In such cases, balanced trees like AVL or Red-Black trees or data structures like B-Trees are better. For non-BST trees, inorder predecessor is undefined or requires full traversal.

Production Patterns

In production, inorder predecessor is used in deletion algorithms to replace a node with two children, maintaining BST properties. It is also used in range queries and nearest smaller value searches. Efficient iterative implementations with parent pointers or threaded trees are common.

Connections

Inorder Successor in BST

Opposite concept; successor is the next node in sorted order after the given node.

Understanding predecessor clarifies successor logic since both rely on BST structure and traversal order.

Doubly Linked List

Similar pattern; predecessor and successor correspond to previous and next nodes in a list.

Knowing linked list navigation helps grasp BST predecessor/successor as tree-based ordered navigation.

Version Control Systems (Git)

Conceptually similar to finding previous commit (predecessor) in a commit history graph.

Recognizing predecessor as 'previous state' in version history helps understand ordered navigation in complex graphs.

Common Pitfalls

#1 Assuming the left child is always the inorder predecessor.

Wrong approach:

fn inorder_predecessor(node: &Option>>) -> Option {
node.as_ref()?.borrow().left.as_ref().map(|left| left.borrow().val)
}

Correct approach:

fn inorder_predecessor(root: Option>>, target: i32) -> Option {
let mut predecessor = None;
let mut current = root.clone();
while let Some(node_rc) = current {
let node = node_rc.borrow();
if node.val < target {
predecessor = Some(node.val);
current = node.right.clone();
} else {
current = node.left.clone();
}
}
predecessor
}

Root cause:

Misunderstanding that predecessor is the largest smaller node, not just the immediate left child.

#2 Not handling the case when the node has no left subtree.

Wrong approach:

fn inorder_predecessor(node: &Option>>) -> Option {
if let Some(left) = node.as_ref()?.borrow().left.clone() {
// find rightmost in left subtree
let mut current = left;
while let Some(right) = current.borrow().right.clone() {
current = right;
}
Some(current.borrow().val)
} else {
None
}
}

Correct approach:

fn inorder_predecessor(root: Option>>, target: i32) -> Option {
let mut predecessor = None;
let mut current = root.clone();
while let Some(node_rc) = current {
let node = node_rc.borrow();
if node.val < target {
predecessor = Some(node.val);
current = node.right.clone();
} else {
current = node.left.clone();
}
}
predecessor
}

Root cause:

Ignoring ancestor traversal when left subtree is missing.

#3 Using recursion without base case or on very deep trees causing stack overflow.

Wrong approach:

fn inorder_predecessor_recursive(node: &Option>>, target: i32) -> Option {
// recursive calls without limit
// may cause stack overflow on deep trees
unimplemented!()
}

Correct approach:

fn inorder_predecessor(root: Option>>, target: i32) -> Option {
let mut predecessor = None;
let mut current = root.clone();
while let Some(node_rc) = current {
let node = node_rc.borrow();
if node.val < target {
predecessor = Some(node.val);
current = node.right.clone();
} else {
current = node.left.clone();
}
}
predecessor
}

Root cause:

Not considering iterative approach for large or unbalanced trees.

Key Takeaways

The inorder predecessor in a BST is the largest node smaller than the given node, found by exploring the left subtree or ancestors.

If the node has a left child, the predecessor is the rightmost node in that left subtree; otherwise, it is an ancestor where the node lies in the right subtree.

Not every node has a predecessor; the smallest node in the BST has none.

Efficient iterative search using BST properties avoids full traversal and stack overflow.

Understanding inorder predecessor is essential for BST operations like deletion and nearest smaller value queries.

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