BST Inorder Predecessor in DSA C# - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root node

↓

Search for target node

↓

Found target node?

No→Return null (no predecessor)

Yes↓

Does target have left child?

Yes→Go to left child

↓

Go to rightmost node in left subtree

↓

Go up to ancestor where target is in right subtree

↓

Return that ancestor as predecessor

Find the node before the target in sorted order by checking left subtree or ancestors.

Execution Sample

DSA C#

Node InorderPredecessor(Node root, Node target) {
  if (target.left != null) {
    return RightmostNode(target.left);
  }
  Node predecessor = null;
  Node current = root;
  while (current != null) {
    if (target.data > current.data) {
      predecessor = current;
      current = current.right;
    } else {
      current = current.left;
    }
  }
  return predecessor;
}

Finds the inorder predecessor of a target node in a BST by checking left subtree or ancestors.

Execution Table

Step	Operation	Current Node	Predecessor Pointer	Visual State
1	Start at root	20	null	20 / \ 10 30
2	Compare target(10) with current(20)	20	null	20 / \ 10 30
3	Target < current, go left	10	null	20 / \ 10 30
4	Target node found	10	null	20 / \ 10 30
5	Check left child of target	10	null	10 has no left child
6	Traverse ancestors to find predecessor	20	null	20 / \ 10 30
7	Target(10) < current(20), go left	10	null	20 / \ 10 30
8	Target(10) > current(10)? No, go left	null	null	Reached null, stop
9	No predecessor found in ancestors	null	null	Predecessor is null
10	Return predecessor	null	null	Result: null (no predecessor)

💡 Traversal ends when current becomes null; predecessor pointer holds the inorder predecessor or null if none.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 7	After Step 8	Final
current	20	20	10	20	10	null	null
predecessor	null	null	null	null	null	null	null
target	10	10	10	10	10	10	10

Key Moments - 3 Insights

Why do we check the left child of the target node first?

Because the inorder predecessor is the rightmost node in the left subtree if it exists, as shown in step 5 of the execution_table.

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

We move up the tree from the root, tracking the last node smaller than the target (predecessor pointer), as in steps 6-9.

Why does the traversal stop when current becomes null?

Because we have reached the end of the path where the predecessor could be; if predecessor is still null, no predecessor exists, as in step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of 'current'?

A 20

B 10

C null

D 30

💡 Hint

Check the 'Current Node' column at step 3 in the execution_table.

At which step does the algorithm determine that the target node has no left child?

A Step 4

B Step 5

C Step 7

D Step 9

💡 Hint

Look for the step where the left child of the target is checked in the execution_table.

If the target node had a left child, which step would show moving to the rightmost node in that subtree?

A Step 5

B Step 6

C Step 2

D Step 10

💡 Hint

Refer to the operation column describing checking the left child of the target.

Concept Snapshot

BST Inorder Predecessor:
- If target has left child, predecessor is rightmost node in left subtree.
- Else, predecessor is ancestor where target is in right subtree.
- Traverse from root to target, track last smaller node.
- Return predecessor or null if none.
- Useful for BST deletion and traversal.

Full Transcript

This visualization shows how to find the inorder predecessor of a node in a binary search tree. We start at the root and search for the target node. If the target has a left child, the predecessor is the rightmost node in that left subtree. If not, we traverse from the root again, tracking the last node smaller than the target. This node is the predecessor. The execution table traces each step, showing current node, predecessor pointer, and tree state. Key moments clarify why we check the left child first and how we find the predecessor if no left child exists. The visual quiz tests understanding of these steps. This method is important for BST operations like deletion.

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 inorder traversal order

   Inorder traversal visits nodes in ascending order for BST.

2. Step 2: Define predecessor in inorder traversal

   The predecessor is the node visited just before the current node, so it must have 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: Predecessor is largest smaller value in BST [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which of the following C# code snippets correctly finds the inorder predecessor of a node with a left subtree in a BST?

easy

A. Node predecessor = node.Left; while (predecessor.Left != null) predecessor = predecessor.Left;

B. Node predecessor = node.Right; while (predecessor.Left != null) predecessor = predecessor.Left;

C. Node predecessor = node.Right; while (predecessor.Right != null) predecessor = predecessor.Right;

D. Node predecessor = node.Left; while (predecessor.Right != null) predecessor = predecessor.Right;

Solution

1. Step 1: Check where predecessor lies if left subtree exists

   Predecessor is the rightmost node in the left subtree.

2. Step 2: Analyze code snippets

   Node predecessor = node.Left; while (predecessor.Right != null) predecessor = predecessor.Right; starts at left child and moves right until no more right child, correctly finding predecessor.

3. Final Answer:

   Node predecessor = node.Left; while (predecessor.Right != null) predecessor = predecessor.Right; -> Option D

4. Quick Check:

   Left subtree's rightmost node = predecessor [OK]

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

Common Mistakes:

• Going left repeatedly instead of right in left subtree
• Starting from right child instead of left
• Ignoring the while loop to find rightmost node

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

       20
      /  \
    10    30
      \
      15

medium

A. 30

B. 10

C. 20

D. 15

Solution

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

   Node 15 has no left child, so predecessor is ancestor smaller than 15.

2. Step 2: Find nearest ancestor smaller than 15

   Ancestor 10 is smaller than 15 and is the closest on the path.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Predecessor of 15 is 10 [OK]

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

Common Mistakes:

• Choosing 20 which is larger than 15
• Choosing 15 itself
• Choosing 30 which is right subtree

4. Consider the following C# method to find the inorder predecessor of a node in a BST. What is the bug?

Node FindPredecessor(Node root, Node node) {
  if (node.Left != null) {
    Node temp = node.Left;
    while (temp.Left != null) {
      temp = temp.Left;
    }
    return temp;
  }
  Node predecessor = null;
  Node current = root;
  while (current != null) {
    if (node.Value > current.Value) {
      predecessor = current;
      current = current.Right;
    } else {
      current = current.Left;
    }
  }
  return predecessor;
}

medium

A. The while loop should check temp.Right, not temp.Left

B. The method does not handle null root

C. The method returns node itself as predecessor

D. The method incorrectly updates predecessor in the else block

Solution

1. Step 1: Analyze left subtree traversal

   Predecessor in left subtree is rightmost node, so loop should move right, not left.

2. Step 2: Identify incorrect loop condition

   Current code loops while temp.Left != null, should be temp.Right != null to find rightmost node.

3. Final Answer:

   The while loop should check temp.Right, not temp.Left -> Option A

4. Quick Check:

   Rightmost node in left subtree = predecessor [OK]

Hint: Go right in left subtree to find predecessor [OK]

Common Mistakes:

• Checking left child repeatedly instead of right
• Ignoring null root case (not critical here)
• Confusing predecessor update logic

5. You want to find the inorder predecessor of a node with value 25 in the BST below:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
      /  
    25   

Which node is the inorder predecessor of 25?

hard

A. 30

B. 10

C. 20

D. 25 has no predecessor

Solution

1. Step 1: Check if node 25 has left subtree

   Node 25 has no left child, so predecessor is ancestor smaller than 25.

2. Step 2: Find nearest ancestor smaller than 25

   Ancestor 20 is smaller than 25 and closest on path from root to 25.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Predecessor of 25 is 20 [OK]

Hint: If no left child, predecessor is nearest smaller ancestor [OK]

Common Mistakes:

• Choosing 30 which is larger than 25
• Choosing 10 which is smaller but not nearest ancestor
• Thinking 25 has no predecessor