Q:

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

mahmoud2506
Save to bookmark
|
2022-05-08
|
  422 
0

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.

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-08
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Data Structure programs using C and C++ (Sorting Programs)
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Implement in-order traversal using C++ program... >>
<< Tower of Hanoi using recursion (C++ program)...