BST Inorder Predecessor in DSA C - Build from Scratch

Find Inorder Predecessor in a BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores unique integer values. You want to find the inorder predecessor of a given node value. The inorder predecessor of a node is the node with the largest value smaller than the given node's value.This is useful in many real-world applications like database indexing and navigation systems where you need to find the previous item in sorted order.

🎯 Goal: Build a C program that creates a BST, sets a target value, finds the inorder predecessor of that value in the BST, and prints the predecessor's value.

📋 What You'll Learn

Create a BST with exact nodes: 20, 10, 30, 5, 15, 25, 35

Set an integer variable target with value 25

Implement a function inorderPredecessor that finds the inorder predecessor of target in the BST

Print the predecessor's value or -1 if no predecessor exists

💡 Why This Matters

🌍 Real World

Finding the inorder predecessor is useful in database systems for range queries and in navigation systems to find the previous location in sorted order.

💼 Career

Understanding BST traversal and predecessor/successor logic is important for software engineers working on search algorithms, database indexing, and system design.

1

Create the BST nodes and build the tree

Create a struct Node with int data, Node *left, and Node *right. Then create nodes with values 20, 10, 30, 5, 15, 25, 35 and link them to form the BST as shown: 20 is root, 10 left child of 20, 30 right child of 20, 5 left child of 10, 15 right child of 10, 25 left child of 30, 35 right child of 30.

DSA C

// Define struct Node and create BST nodes with exact values and links
// Your code here

Hint

Start by defining the Node structure. Then create each node as a variable and link them by assigning the left and right pointers.

2

Set the target value to find its inorder predecessor

Create an integer variable called target and set it to 25.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node node5 = {5, NULL, NULL};
Node node15 = {15, NULL, NULL};
Node node25 = {25, NULL, NULL};
Node node35 = {35, NULL, NULL};
Node node10 = {10, &node5, &node15};
Node node30 = {30, &node25, &node35};
Node node20 = {20, &node10, &node30};

Node *root = &node20;

// Create an integer variable target and set it to 25
// Your code here

Hint

Just declare an integer variable named target and assign it the value 25.

3

Implement the function to find the inorder predecessor

Write a function Node* inorderPredecessor(Node *root, int target) that returns the pointer to the inorder predecessor node of target in the BST. Use the BST property to traverse the tree. If the node with target has a left subtree, the predecessor is the rightmost node in that left subtree. Otherwise, track the last node smaller than target while searching.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node node5 = {5, NULL, NULL};
Node node15 = {15, NULL, NULL};
Node node25 = {25, NULL, NULL};
Node node35 = {35, NULL, NULL};
Node node10 = {10, &node5, &node15};
Node node30 = {30, &node25, &node35};
Node node20 = {20, &node10, &node30};

Node *root = &node20;

int target = 25;

// Implement Node* inorderPredecessor(Node *root, int target) function
// Your code here

Hint

First find the node with the target value. If it has a left child, find the rightmost node in that left subtree. Otherwise, track the last node smaller than target while traversing from root.

4

Print the inorder predecessor's value

Call inorderPredecessor(root, target) and print the predecessor's data. If the predecessor is NULL, print -1.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node node5 = {5, NULL, NULL};
Node node15 = {15, NULL, NULL};
Node node25 = {25, NULL, NULL};
Node node35 = {35, NULL, NULL};
Node node10 = {10, &node5, &node15};
Node node30 = {30, &node25, &node35};
Node node20 = {20, &node10, &node30};

Node *root = &node20;

int target = 25;

Node* findNode(Node *root, int target) {
    if (root == NULL) return NULL;
    if (root->data == target) return root;
    else if (target data) return findNode(root->left, target);
    else return findNode(root->right, target);
}

Node* rightmost(Node *node) {
    while (node && node->right != NULL) {
        node = node->right;
    }
    return node;
}

Node* inorderPredecessor(Node *root, int target) {
    Node *current = findNode(root, target);
    if (current == NULL) return NULL;

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

// Call inorderPredecessor and print the result
// Your code here

Hint

Call the inorderPredecessor function with root and target. If the result is not NULL, print the data of the predecessor. Otherwise, print -1.

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