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.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The node with the smallest value larger than the given node

B. The node with the largest value smaller 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 B

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before in sorted order [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++ function signatures correctly represents a function to find the inorder predecessor of a BST node given its pointer Node* root and Node* target?

easy

A. Node* findInorderPredecessor(Node* root, Node* target);

B. void findInorderPredecessor(Node* root, int target);

C. int findInorderPredecessor(Node* root, Node* target);

D. Node findInorderPredecessor(Node root, Node target);

Solution

1. Step 1: Analyze parameter types

   The function needs the root pointer and the target node pointer to find the predecessor.

2. Step 2: Analyze return type

   The predecessor is a node pointer, so return type should be Node*.

3. Final Answer:

   Node* findInorderPredecessor(Node* root, Node* target); -> Option A

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Return pointer to predecessor node [OK]

Common Mistakes:

• Using int return type instead of Node*
• Passing target as int instead of Node*
• Passing nodes by value instead of pointer

3. Consider the following BST and code snippet to find the inorder predecessor of node with value 15:

struct Node {
  int val;
  Node* left;
  Node* right;
};

Node* findMax(Node* root) {
  while (root->right) root = root->right;
  return root;
}

Node* inorderPredecessor(Node* root, Node* target) {
  if (target->left) return findMax(target->left);
  Node* predecessor = nullptr;
  while (root) {
    if (target->val > root->val) {
      predecessor = root;
      root = root->right;
    } else if (target->val < root->val) {
      root = root->left;
    } else break;
  }
  return predecessor;
}

// BST structure:
//        20
//       /  \
//     10    30
//       \     \
//       15    40

Node* root = ...; // root of above BST
Node* target = root->left->right; // node with value 15
Node* pred = inorderPredecessor(root, target);
std::cout << pred->val << std::endl;

What is the output?

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Check if target has left subtree

   Node 15 has no left child, so we skip findMax on left subtree.

2. Step 2: Traverse from root to find predecessor

   Start at root (20). Since 15 < 20, go left to 10. Since 15 > 10, set predecessor = 10 and go right to 15. Found target, stop.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Largest smaller value than 15 is 10 [OK]

Hint: If no left child, track last smaller ancestor [OK]

Common Mistakes:

• Returning target node itself
• Returning root node 20 incorrectly
• Confusing predecessor with successor

4. The following code attempts to find the inorder predecessor of a node in a BST but has a bug. Identify the bug.

Node* inorderPredecessor(Node* root, Node* target) {
  if (target->left) {
    Node* temp = target->left;
    while (temp->left) temp = temp->left;
    return temp;
  }
  Node* predecessor = nullptr;
  while (root) {
    if (target->val > root->val) {
      predecessor = root;
      root = root->right;
    } else if (target->val < root->val) {
      root = root->left;
    } else break;
  }
  return predecessor;
}

medium

A. The predecessor variable is not initialized

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

C. The function returns nullptr always

D. The loop to find max in left subtree incorrectly goes left instead of right

Solution

1. Step 1: Check left subtree max search

   To find inorder predecessor in left subtree, we must find the maximum node, which is the rightmost node, but code goes left repeatedly.

2. Step 2: Confirm other parts are correct

   The rest of the code correctly handles cases without left subtree and initializes predecessor.

3. Final Answer:

   The loop to find max in left subtree incorrectly goes left instead of right -> Option D

4. Quick Check:

   Max in left subtree requires right traversal [OK]

Hint: Max in left subtree means go right, not left [OK]

Common Mistakes:

• Going left instead of right to find max
• Not checking if target->left is null
• Confusing predecessor with successor

5. Given a BST with nodes inserted in this order: 25, 15, 50, 10, 22, 35, 70, 4, 12, 18, 24, 31, 44, 66, 90. Write a function to find the inorder predecessor of a node with value 31. What will be the predecessor's value? Hint: Use the BST property and consider both cases when the node has a left subtree or not.

hard

A. 25

B. 35

C. 24

D. 22

Solution

1. Step 1: Locate node 31

   Node 31 is the left child of 35 and has no left subtree.

2. Step 2: Traverse from root to find predecessor

   Start at root 25 (31 > 25, predecessor=25, go right to 50). 31 < 50, go left to 35. 31 < 35, go left to 31. Found target, predecessor=25.

3. Step 3: Verify with inorder traversal

   Inorder traversal sequence around 31 is ... 24, 25, 31, 35 ... The predecessor of 31 is the largest smaller value, which is 24 (left subtree of 25).

4. Final Answer:

   24 -> Option C

5. Quick Check:

   Inorder predecessor of 31 is 24 [OK]

Hint: If no left child, predecessor is last smaller ancestor or max in left subtree [OK]

Common Mistakes:

• Choosing 25 instead of 24
• Choosing successor 35 instead of predecessor
• Ignoring left subtree check