BST Inorder Predecessor in DSA C

Mental Model

The inorder predecessor of a node in a BST is the node with the next smaller value when we list all nodes in order.

Analogy: Imagine a sorted list of books on a shelf. The inorder predecessor of a book is the book immediately to its left.

       20
      /  \
    10    30
   /  \     \
  5   15    40
 ↑curr

Dry Run Walkthrough

Input: BST with nodes 20, 10, 30, 5, 15, 40; find inorder predecessor of node 20

Goal: Find the node with the largest value smaller than 20

Step 1: Start at node 20, check left subtree for predecessor

       20
      /  \
    10    30
   /  \     \
  5   15    40
 ↑curr=20

Why: Predecessor must be smaller, so look left

Step 2: Move to left child 10, then go right as far as possible

       20
      /  \
    10    30
   /  \     \
  5   15    40
       ↑curr=10

Why: Rightmost node in left subtree is predecessor

Step 3: Move right from 10 to 15, no further right child

       20
      /  \
    10    30
   /  \     \
  5   15    40
           ↑curr=15

Why: 15 is the largest node smaller than 20

Result:

       20
      /  \
    10    30
   /  \     \
  5   15    40

Inorder predecessor of 20 is 15

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define BST node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert node in BST
Node* insert(Node* root, int data) {
    if (root == NULL) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

// Find inorder predecessor
Node* inorderPredecessor(Node* root, int key) {
    Node* curr = root;
    Node* predecessor = NULL;

    // First find the node with key
    while (curr != NULL && curr->data != key) {
        if (key < curr->data) curr = curr->left;
        else curr = curr->right;
    }

    if (curr == NULL) return NULL; // key not found

    // Case 1: If left subtree exists, predecessor is rightmost node in left subtree
    if (curr->left != NULL) {
        predecessor = curr->left;
        while (predecessor->right != NULL) {
            predecessor = predecessor->right; // move right to find max
        }
        return predecessor;
    }

    // Case 2: No left subtree, predecessor is ancestor where current node is in right subtree
    Node* ancestor = root;
    predecessor = NULL;
    while (ancestor != curr) {
        if (curr->data > ancestor->data) {
            predecessor = ancestor; // potential predecessor
            ancestor = ancestor->right;
        } else {
            ancestor = ancestor->left;
        }
    }
    return predecessor;
}

// Print result
void printPredecessor(Node* root, int key) {
    Node* pred = inorderPredecessor(root, key);
    if (pred != NULL) printf("Inorder predecessor of %d is %d\n", key, pred->data);
    else printf("No inorder predecessor for %d\n", key);
}

int main() {
    Node* root = NULL;
    int values[] = {20, 10, 30, 5, 15, 40};
    int n = sizeof(values)/sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }
    printPredecessor(root, 20);
    return 0;
}

while (curr != NULL && curr->data != key) { if (key < curr->data) curr = curr->left; else curr = curr->right; }

Locate the node with the given key

if (curr->left != NULL) { predecessor = curr->left; while (predecessor->right != NULL) predecessor = predecessor->right; return predecessor; }

If left subtree exists, find rightmost node there as predecessor

Node* ancestor = root; predecessor = NULL; while (ancestor != curr) { if (curr->data > ancestor->data) { predecessor = ancestor; ancestor = ancestor->right; } else { ancestor = ancestor->left; } }

If no left subtree, find deepest ancestor smaller than current node

Output

Inorder predecessor of 20 is 15

Complexity Analysis

Time: O(h) because we traverse from root to node and possibly down one subtree, where h is tree height

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive approach would do full inorder traversal O(n), this method is faster by using BST properties

Edge Cases

Node has no left subtree and is the smallest node

No predecessor found, function returns NULL

DSA C

if (curr == NULL) return NULL;

Node not present in BST

Function returns NULL indicating no predecessor

DSA C

if (curr == NULL) return NULL;

Node has left subtree with only one node

That single left child is predecessor

DSA C

if (curr->left != NULL) { predecessor = curr->left; while (predecessor->right != NULL) predecessor = predecessor->right; return predecessor; }

When to Use This Pattern

When asked to find the previous smaller node in BST order, use inorder predecessor pattern by checking left subtree or ancestors.

Common Mistakes

Mistake: Not checking if the node with given key exists before searching predecessor
Fix: Add a search step to find the node first and return NULL if not found

Mistake: Assuming predecessor is always in left subtree without checking ancestors
Fix: Handle case where no left subtree exists by tracking ancestors smaller than node

Summary

Finds the node with the next smaller value than a given node in a BST.

Use when you need to find the immediate predecessor in sorted order in a BST.

The predecessor is either the rightmost node in left subtree or the deepest ancestor smaller than the node.

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