BST Inorder Predecessor in DSA Rust - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root node

↓

Find node with given key

↓

Does node have left child?

No→Go up to parent until node is right child

|Yes↓

Go to left child

↓

Go to rightmost node in left subtree

↓

This node is inorder predecessor

↓

Return predecessor value

Find the node, then if it has a left child, go left once and then right as far as possible. Otherwise, move up to find the nearest ancestor where the node is in the right subtree.

Execution Sample

DSA Rust

fn inorder_predecessor(root: &Option<Box<Node>>, key: i32) -> Option<i32> {
    // Find node with key
    // If left child exists, go left then rightmost
    // Else go up to parent until node is right child
    None // placeholder return
}

This code finds the inorder predecessor of a node with given key in a BST.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root	50	head=root(50)	50 / \ 30 70
2	Find node with key=30	50 -> 30	move left from 50 to 30	50 / \ 30 70
3	Node 30 has left child?	30	check left child	30 has left child 20
4	Go to left child	20	move left from 30 to 20	50 / \ 30 70 / 20
5	Go to rightmost node in left subtree	20	20 has no right child	20 is rightmost in left subtree
6	Return predecessor value	20	predecessor=20	Predecessor of 30 is 20
7	Find node with key=70	50 -> 70	move right from 50 to 70	50 / \ 30 70
8	Node 70 has left child?	70	check left child	70 has left child 60
9	Go to left child	60	move left from 70 to 60	70 / 60
10	Go to rightmost node in left subtree	60	60 has no right child	60 is rightmost in left subtree
11	Return predecessor value	60	predecessor=60	Predecessor of 70 is 60
12	Find node with key=20	50 -> 30 -> 20	move left from 50 to 30, then left to 20	20 has no left child
13	Node 20 has left child?	20	check left child	No left child
14	Go up to parent until node is right child	20 -> 30	20 is left child of 30, move up	No predecessor in left subtree
15	Go up to parent until node is right child	30 -> 50	30 is left child of 50, move up	No predecessor found
16	No predecessor found	None	Reached root without right child relation	Predecessor does not exist
17	End	None	return None	End of search

💡 Search ends when predecessor found or no predecessor exists (node has no left child and no suitable ancestor).

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 9	After Step 12	After Step 14	Final
current_node	50	30	20	70	60	20	30	None
predecessor	None	None	None	None	None	None	None	None or value
parent_node	None	50	30	50	70	30	50	None

Key Moments - 3 Insights

Why do we go to the rightmost node in the left subtree?

Because the inorder predecessor is the largest node smaller than the current node, which is the rightmost node in its left subtree (see execution_table step 5 and 10).

What if the node has no left child? How do we find the predecessor?

We move up to the parent until we find a node that is a right child of its parent. That parent is the predecessor (see execution_table steps 14-16).

Why might there be no inorder predecessor?

If the node is the smallest in the BST (like 20 in the example), it has no left child and no ancestor where it is a right child, so no predecessor exists (see execution_table step 16).

Visual Quiz - 3 Questions

Look at the execution_table, what is the predecessor of node 30 at step 6?

A 20

B 30

C 50

D None

💡 Hint

Check the Visual State and Pointer Changes columns at step 6.

At which step does the search conclude there is no predecessor for node 20?

A Step 14

B Step 16

C Step 12

D Step 10

💡 Hint

Look for the step where 'No predecessor found' is noted in Visual State.

If node 70 had no left child, what would be the next step according to the concept_flow?

A Go to rightmost node in left subtree

B Return None immediately

C Go up to parent until node is right child

D Return the node itself

💡 Hint

Refer to the decision after checking if node has left child in concept_flow.

Concept Snapshot

BST Inorder Predecessor:
- Find node with given key
- If node has left child: go left once, then rightmost down
- Else: move up to parent until node is right child
- If none found, predecessor does not exist
- Returns the largest smaller value than the node

Full Transcript

To find the inorder predecessor in a BST, start at the root and find the node with the given key. If the node has a left child, move to that left child and then keep moving right until no more right children exist; this rightmost node is the predecessor. If the node has no left child, move up the tree to the parent nodes until you find a node that is a right child of its parent; that parent is the predecessor. If no such node exists, the predecessor does not exist. This process ensures finding the largest value smaller than the given node's value.

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