Q:

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

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.

 

All Answers

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)

Implement in-order traversal using C++ program... >>
<< Tower of Hanoi using recursion (C++ program)...