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

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 found predecessor node

↓

Done

Find the inorder predecessor of a node in a BST by searching the node, then either going to the rightmost node in its left subtree or moving up to the ancestor where the node is in the right subtree.

Execution Sample

DSA C

Node* inorderPredecessor(Node* root, int key) {
  Node* current = root;
  Node* predecessor = NULL;
  while (current && current->data != key) {
    if (key < current->data) current = current->left;
    else {
      predecessor = current;
      current = current->right;
    }
  }
  if (!current) return NULL;
  if (current->left) {
    predecessor = current->left;
    while (predecessor->right) predecessor = predecessor->right;
    return predecessor;
  }
  return predecessor;
}

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

Execution Table

Step	Operation	Current Node	Predecessor Pointer	Visual State
1	Start at root	20	NULL	20 / \ 10 30
2	Compare key=15 with 20	20	NULL	20 / \ 10 30
3	Go left since 15 < 20	10	NULL	20 / \ 10 30
4	Compare key=15 with 10	10	NULL	20 / \ 10 30
5	Go right since 15 > 10	15	10	20 / \ 10 30 \ 15
6	Found node with key=15	15	10	20 / \ 10 30 \ 15
7	Node 15 has no left child	15	10	20 / \ 10 30 \ 15
8	Return predecessor pointer 10	15	10	Predecessor is 10

💡 Search ends when current is NULL or node with key found; predecessor returned accordingly.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 7	Final
current	20	20	10	15	15	15	15
predecessor	NULL	NULL	NULL	10	10	10	10

Key Moments - 3 Insights

Why do we update predecessor when moving right but not when moving left during search?

Because when moving right, the current node could be a potential predecessor (smaller than key but closest), as shown in execution_table step 5 where predecessor updates to 10.

What if the target node has a left subtree? How do we find the predecessor?

We go to the left child, then keep moving right until no more right child exists, to find the rightmost node in left subtree.

What happens if the node with the key does not exist in the BST?

The search ends with current NULL (not shown in this simplified table), and the function returns NULL indicating no predecessor.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the value of predecessor?

A 20

B NULL

C 10

D 15

💡 Hint

Check the 'Predecessor Pointer' column at step 5 in execution_table.

At which step does the search stop because current becomes NULL?

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look for the step where 'Current Node' is NULL and operation says 'stop search' in execution_table.

Which step shows the case when the target node has no left child?

A Step 7

B Step 3

C Step 9

D Step 10

💡 Hint

Look at step 7 in the execution_table: 'Node 15 has no left child'.

Concept Snapshot

BST Inorder Predecessor:
- Find node with given key.
- If node has left child, predecessor is rightmost node in left subtree.
- Else, predecessor is ancestor where node is in right subtree.
- Return NULL if node not found or no predecessor.
- Used in BST deletion and traversal.

Full Transcript

To find the inorder predecessor of a node in a BST, first search for the node by comparing the key with current node data. If the key is less, go left; if greater, go right and update predecessor pointer. When found, if the node has a left child, move to that left child and then go as far right as possible to find the predecessor. If no left child, the predecessor is the last recorded ancestor where we moved right. If the node is not found, return NULL. This process helps find the immediate smaller node in BST order.

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 in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node visited just before it in 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: 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 given node node in a BST when the node has a left subtree?

easy

A. Node* pred = node->left; while (pred->right != NULL) pred = pred->right;

B. Node* pred = node->right; while (pred->left != NULL) pred = pred->left;

C. Node* pred = node->left; while (pred->left != NULL) pred = pred->left;

D. Node* pred = node->right; while (pred->right != NULL) pred = pred->right;

Solution

1. Step 1: Identify inorder predecessor in left subtree

   If node has a left child, predecessor is the rightmost node in left subtree.

2. Step 2: Trace code logic

   Starting from node->left, moving right until right child is NULL finds the rightmost node.

3. Final Answer:

   Node* pred = node->left; while (pred->right != NULL) pred = pred->right; -> Option A

4. Quick Check:

   Left subtree's rightmost node = predecessor [OK]

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

Common Mistakes:

• Going right subtree instead of left
• Moving left repeatedly instead of right
• Starting from node->right instead of node->left

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

        20
       /  \
     10    30
       \     \
       15    40

medium

A. 30

B. 15

C. 20

D. 10

Solution

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

   Node 15 has no left child, so predecessor is an 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 to root.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Predecessor of 15 is 10 [OK]

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

Common Mistakes:

• Choosing node itself as predecessor
• Choosing larger ancestor like 20
• Confusing predecessor with successor

4. Consider this buggy C function to find the inorder predecessor of a node in a BST:

Node* inorderPredecessor(Node* root, Node* node) {
    if (node->left != NULL) {
        Node* pred = node->left;
        while (pred->left != NULL) {
            pred = pred->left;
        }
        return pred;
    }
    Node* pred = NULL;
    Node* ancestor = root;
    while (ancestor != node) {
        if (node->data > ancestor->data) {
            pred = ancestor;
            ancestor = ancestor->right;
        } else {
            ancestor = ancestor->left;
        }
    }
    return pred;
}

What is the main error in this code?

medium

A. The ancestor traversal is incorrect and may cause infinite loop

B. The function does not handle the case when node has no left subtree

C. The while loop should move right in left subtree, not left

D. The function returns NULL even if predecessor exists

Solution

1. Step 1: Analyze left subtree traversal

   In left subtree, predecessor is rightmost node, so loop should move right, not left.

2. Step 2: Check code loop

   Code incorrectly moves left repeatedly, so it finds leftmost node instead of rightmost.

3. Final Answer:

   The while loop should move right in left subtree, not left -> Option C

4. Quick Check:

   Left subtree traversal must go right for predecessor [OK]

Hint: In left subtree, go right to find predecessor [OK]

Common Mistakes:

• Moving left instead of right in left subtree
• Ignoring ancestor traversal logic
• Assuming predecessor is always left child

5. You have a BST where each node has a pointer to its parent. Write the logic to find the inorder predecessor of a node node that has no left child. Which approach correctly finds the predecessor?

hard

A. Return the right child of the node's parent

B. Move up using parent pointers until you find a node which is right child of its parent; then return that parent

C. Move up using parent pointers until you find a node which is left child of its parent; then return that parent

D. Return the left child of the node's parent

Solution

1. Step 1: Understand no left child case

   If node has no left child, predecessor is an ancestor where node is in right subtree.

2. Step 2: Use parent pointers to find such ancestor

   Move up until current node is right child of its parent; that parent is predecessor.

3. Final Answer:

   Move up using parent pointers until you find a node which is right child of its parent; then return that parent -> Option B

4. Quick Check:

   Go up to right-child parent for predecessor [OK]

Hint: Go up until node is right child, then parent is predecessor [OK]

Common Mistakes:

• Stopping at left child parent
• Returning sibling nodes incorrectly
• Assuming predecessor is always child node