# 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 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