Find in-order Successor and Predecessor in a BST using C++ program

In this tutorial, we will learn how to find in-order successor and predecessor in BST (Binary Search Tree) using C++ program? By Shubham Singh Rajawat Last updated : August 09, 2023

Successor and Predecessor

Predecessor means the node that lies just behind the given node and Successor means the node that lies just after the given node.

In-order traversal

An in-order traversal is a traversal in which nodes are traversed in the format Left Root Right.

Algorithm

Step 1: start with root of the tree

Step 2: if the given node is equal to root, then for the in-order predecessor go to the right most node of the left child of the root and for the in-order successor go to the left most node of the right child of the root.

Step 3: if the given node is greater than the root, then update predecessor equal to root and root equal to its right child and search the subtree(current tree).

Step 4: if the given node is less than the root, then update successor equal to root and root equal to its left child and search the subtree(current tree).

C++ program to find in-order Successor and Predecessor in a BST

In this example, we are finding in-order successor and predecessor in BST (Binary Search Tree) using the C++ program.

#include <iostream>
using namespace std;

/*structure of the tree*/
struct node {
    int info;
    node *left, *right;
};

/*Method to find the predecessor and successor*/
void find(node* root, node*& pre, node*& suc, int info)
{
    if (root == NULL) {
        return;
    }

    /*if key(the given node) is the root*/
    if (root->info == info) {
        if (root->left != NULL) {
            node* temp = root->left;
            while (temp->right != NULL) {
                temp = temp->right;
            }
            pre = temp;
        }
        if (root->right != NULL) {
            node* temp = root->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            suc = temp;
        }
        return;
    }

    /*if key is less than current node(root)*/
    if (root->info > info) {
        suc = root;
        /*Search the left subtree*/
        find(root->left, pre, suc, info);
    }
    /*if key is greater than current node(root)*/
    else {
        pre = root;
        /*Search the right subtree*/
        find(root->right, pre, suc, info);
    }
}

/*Method to create a newNode if a tree does not exist*/
node* newNode(int n)
{
    node* p = new node;
    p->info = n;
    p->left = p->right = NULL;
    return p;
}

/*Method to insert node in the BST */
node* insert(node* node, int info)
{
    if (node == NULL) {
        return newNode(info);
    }
    if (info < node->info) {
        node->left = insert(node->left, info);
    }
    else {
        node->right = insert(node->right, info);
    }
    return node;
}

//main program
int main()
{
    int info = 70;

    node* root = newNode(60);
    insert(root, 50);
    insert(root, 70);
    insert(root, 40);
    insert(root, 30);
    insert(root, 75);
    insert(root, 80);
    insert(root, 65);
    insert(root, 45);
    insert(root, 55);
    insert(root, 90);
    insert(root, 67);

    /*pre will contain predecessor and suc will contain successor*/
    node *pre = NULL, *suc = NULL; 

    find(root, pre, suc, info);
    if (pre != NULL) {
        cout << "Predecessor of " << info << " is " << pre->info << endl;
    }
    else {
        cout << "!!!!!!No possible predecessor!!!!!!";
    }

    if (suc != NULL) {
        cout << "Successor of " << info << " is " << suc->info << endl;
    }
    else {
        cout << "!!!!!!No possible successor!!!!!!";
    }
    cout << endl;

    return 0;
}

Output

Predecessor of 70 is 67
Successor of 70 is 75