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

In this post, we are going to learn how to find in-order successor and predecessor in BST (Binary Search Tree) using C++ program?
Submitted by Shubham Singh Rajawat, on July 24, 2017

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

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).

Consider the given 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);

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

	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