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

BST Inorder Successor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the next bigger number after a given number in the tree. This is called the inorder successor.Imagine the BST as a sorted list of numbers arranged in a tree shape. Finding the inorder successor means finding the number that comes right after a given number when you look at the tree in sorted order.

🎯 Goal: Build a program that creates a BST, sets a target node, finds the inorder successor of that node, and prints the successor's value or -1 if there is none.

📋 What You'll Learn

Create a BST with the exact nodes: 20, 9, 25, 5, 12, 11, 14

Create a pointer called target pointing to the node with value 9

Implement a function inorderSuccessor that finds the inorder successor of target in the BST

Print the value of the inorder successor node or -1 if no successor exists

💡 Why This Matters

🌍 Real World

Finding the inorder successor is useful in database indexing, scheduling tasks in order, and navigating sorted data efficiently.

💼 Career

Understanding BST operations like inorder successor is important for software engineers working with search trees, databases, and algorithms.

1

Create the BST nodes and build the tree

Create the BST nodes with values 20, 9, 25, 5, 12, 11, 14 using the TreeNode struct. Connect them to form the BST exactly as follows:
20 is root, 9 is left child of 20, 25 is right child of 20, 5 is left child of 9, 12 is right child of 9, 11 is left child of 12, 14 is right child of 12.
Use pointers named exactly as root, node9, node25, node5, node12, node11, node14.

DSA C++

#include 
using namespace std;

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

int main() {

    // Create BST nodes and connect them
    // Your code here

    return 0;
}

Hint

Use new TreeNode(value) to create nodes. Connect children using parent->left = child or parent->right = child.

2

Set the target node pointer

Create a pointer called target and set it to point to the node with value 9, which is node9.

DSA C++

#include 
using namespace std;

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

int main() {
    TreeNode* root = new TreeNode(20);
    TreeNode* node9 = new TreeNode(9);
    TreeNode* node25 = new TreeNode(25);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node12 = new TreeNode(12);
    TreeNode* node11 = new TreeNode(11);
    TreeNode* node14 = new TreeNode(14);

    root->left = node9;
    root->right = node25;
    node9->left = node5;
    node9->right = node12;
    node12->left = node11;
    node12->right = node14;

    // Set target pointer to node9
    // Your code here

    return 0;
}

Hint

Just assign target = node9; to point to the node with value 9.

3

Implement the inorderSuccessor function

Write a function TreeNode* inorderSuccessor(TreeNode* root, TreeNode* target) that finds the inorder successor of target in the BST rooted at root. Use the BST property to find the successor without traversing the whole tree.

Inside main(), call inorderSuccessor(root, target) and store the result in a pointer called successor.

DSA C++

#include 
using namespace std;

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

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* target) {
    // Implement the inorderSuccessor function here
    // Your code here
}

int main() {
    TreeNode* root = new TreeNode(20);
    TreeNode* node9 = new TreeNode(9);
    TreeNode* node25 = new TreeNode(25);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node12 = new TreeNode(12);
    TreeNode* node11 = new TreeNode(11);
    TreeNode* node14 = new TreeNode(14);

    root->left = node9;
    root->right = node25;
    node9->left = node5;
    node9->right = node12;
    node12->left = node11;
    node12->right = node14;

    TreeNode* target = node9;

    // Call inorderSuccessor and store in successor
    // Your code here

    return 0;
}

Hint

Use a pointer successor to track the next bigger node. Move left or right depending on comparison with target->val.

4

Print the inorder successor value

Print the value of the successor node if it exists. If successor is nullptr, print -1.

DSA C++

#include 
using namespace std;

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

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* target) {
    TreeNode* successor = nullptr;
    TreeNode* current = root;
    while (current != nullptr) {
        if (target->val val) {
            successor = current;
            current = current->left;
        } else {
            current = current->right;
        }
    }
    return successor;
}

int main() {
    TreeNode* root = new TreeNode(20);
    TreeNode* node9 = new TreeNode(9);
    TreeNode* node25 = new TreeNode(25);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node12 = new TreeNode(12);
    TreeNode* node11 = new TreeNode(11);
    TreeNode* node14 = new TreeNode(14);

    root->left = node9;
    root->right = node25;
    node9->left = node5;
    node9->right = node12;
    node12->left = node11;
    node12->right = node14;

    TreeNode* target = node9;

    TreeNode* successor = inorderSuccessor(root, target);

    // Print successor value or -1 if none
    // Your code here

    return 0;
}

Hint

Use cout to print successor->val if successor is not nullptr. Otherwise, print -1.