BST Inorder Predecessor in DSA C++ - Build from Scratch

BST Inorder Predecessor

📖 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 or navigation systems where you want to find the closest smaller key.

🎯 Goal: Build a program that creates a BST, sets a target value, finds the inorder predecessor of that target value in the BST, and prints the predecessor's value or -1 if no predecessor exists.

📋 What You'll Learn

Create a BST by inserting nodes with these exact values in order: 20, 10, 30, 5, 15, 25, 35

Create an integer variable target with the value 15

Implement a function inorderPredecessor that takes the BST root and target and returns the inorder predecessor value or -1 if none

Print the inorder predecessor value

💡 Why This Matters

🌍 Real World

Finding the inorder predecessor is useful in database indexing, memory management, and navigation systems where you need to find the closest smaller key or value.

💼 Career

Understanding BST operations like inorder predecessor is important for software engineers working on search algorithms, data storage, and optimization problems.

1

Create the BST with given nodes

Create a struct Node with int val, Node* left, and Node* right. Then create a function insertNode that inserts a value into the BST. Finally, create a BST by inserting nodes with these exact values in order: 20, 10, 30, 5, 15, 25, 35. Store the root in a variable called root.

DSA C++

// Define Node struct
// Define insertNode function
// Insert nodes 20, 10, 30, 5, 15, 25, 35 into BST
// Your code here

Hint

Start by defining the Node struct with value and pointers. Then write insertNode to place values correctly in BST. Insert nodes one by one to build the tree.

2

Set the target value

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

DSA C++

#include 
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* insertNode(Node* root, int val) {
    if (!root) return new Node(val);
    if (val val) root->left = insertNode(root->left, val);
    else root->right = insertNode(root->right, val);
    return root;
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 20);
    root = insertNode(root, 10);
    root = insertNode(root, 30);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 25);
    root = insertNode(root, 35);

    int target = 0; // Set target to 15
    // Your code here

    return 0;
}

Hint

Just create an integer variable named target and assign it the value 15.

3

Implement the inorder predecessor function

Implement a function called inorderPredecessor that takes Node* root and int target as parameters and returns an int. This function should find and return the inorder predecessor value of the target in the BST. If no predecessor exists, return -1. Use the BST property to find the predecessor efficiently.

DSA C++

#include 
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* insertNode(Node* root, int val) {
    if (!root) return new Node(val);
    if (val val) root->left = insertNode(root->left, val);
    else root->right = insertNode(root->right, val);
    return root;
}

int inorderPredecessor(Node* root, int target) {
    // Your code here
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 20);
    root = insertNode(root, 10);
    root = insertNode(root, 30);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 25);
    root = insertNode(root, 35);

    int target = 15;

    // Your code here

    return 0;
}

Hint

Use a pointer predecessor to track the last node smaller than target. Traverse the tree starting from root. If current node's value is less than target, update predecessor and go right. Otherwise, go left. Return the predecessor's value or -1 if none.

4

Print the inorder predecessor

Use cout to print the value returned by inorderPredecessor(root, target).

DSA C++

#include 
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* insertNode(Node* root, int val) {
    if (!root) return new Node(val);
    if (val val) root->left = insertNode(root->left, val);
    else root->right = insertNode(root->right, val);
    return root;
}

int inorderPredecessor(Node* root, int target) {
    Node* predecessor = nullptr;
    Node* current = root;
    while (current) {
        if (target val) {
            current = current->left;
        } else {
            predecessor = current;
            current = current->right;
        }
    }
    return predecessor ? predecessor->val : -1;
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 20);
    root = insertNode(root, 10);
    root = insertNode(root, 30);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    root = insertNode(root, 25);
    root = insertNode(root, 35);

    int target = 15;

    int pred = inorderPredecessor(root, target);

    cout << pred << endl; // Print the predecessor value

    return 0;
}

Hint

Use cout to print the value returned by inorderPredecessor(root, target). The expected output is the predecessor value or -1 if none.