How to find inorder successor in a binary search tree, sample C/C++ code would be helpful?

+1 vote
215 views
How to find inorder successor in a binary search tree, sample C/C++ code would be helpful?
posted May 16, 2016

First comes the left sub tree then root node and right subtree
@Farheen: Can you share the sample code?

+1 vote

Hi,to find the inorder successor of BST we should follow these steps:
step 1: Find the current node for which you want its successor.
step 2: if the current node is null then return null as it is the last node.
step 3: if there is right subtree in current node then return find minimum and this minimum value will be successor of current node.
step 4: otherwise create ancestor and successor node and update the ancestor with root node and successor with null.
step 5: you can use recursive calls to find its successor Or a loop to reach successor.(I am using a loop to get inorder successor)

``````node *successor=new node();
successor=NULL;
node *ancestor=new node();
ancestor=root;
while(ancestor!=current)    // current holds the address to node for which you want successor
{
if(current->data < ancestor->data)
{
successor=ancestor;   // for this current node will be in left always;
ancestor=ancestor->left;
}
else{
ancestor=ancestor->right;
}
}
return successor;
``````

Find code below to get inorder successor of given node in BST in c++

``````#include<bits/stdc++.h>
struct node{
int data;
node *left;
node *right;
//node *parent;
};
node *getNewNode(int value)
{
node *newnode=new node();
newnode->data=value;
newnode->left=NULL;
newnode->right=NULL;
// newnode->parent=NULL;
return newnode;
}
void display(node *display_node)
{

if(display_node!=NULL)
{
if(display_node->left!=NULL)
{
display(display_node->left);
}
printf("%d\t",display_node->data);
if(display_node->right!=NULL)
{
display(display_node->right);
}
}
}
node *insert_node(node *root_node,int value)
{
if(root_node==NULL)
{
root_node=getNewNode(value);
}
else if(value <= root_node->data)
{
root_node->left=insert_node(root_node->left,value);
}
else if(value> root_node->data){
root_node->right=insert_node(root_node->right,value);
}
//display(root_node);
return root_node;
}
node *FindMin(node *findmin)
{
if(findmin->left)
{
FindMin(findmin->left);
}
return findmin;
}
node *findCurrentNode(node *givennode,int curr_value)
{
if(curr_value==givennode->data)
{
return givennode;
}
else if(givennode->data >curr_value){
return findCurrentNode(givennode->left,curr_value);
}
else if(givennode->data <curr_value){
return findCurrentNode(givennode->right,curr_value);
}
else{
return givennode;
}
}
node *getSuccessor(node *getsuccessor,int value)
{
struct node *current=new node();
current=findCurrentNode(getsuccessor,value);
printf("Current Node Value=%d\n",current->data);
if(current==NULL){
// printf("NULL\n");
return NULL;
}
if(current->right!=NULL) // node has right subtree
{
return FindMin(getsuccessor->right);
}
else{
node *successor=new node();
successor=NULL;
node *ancestor=new node();
ancestor=getsuccessor; // root node is getsuccessor
while(ancestor!=current)
{
if(current->data < ancestor->data)
{
successor=ancestor;   // for this current node will be in left always;
ancestor=ancestor->left;
}
else{
ancestor=ancestor->right;
}
}
return successor;
}
}
int main()
{
int numberofnodes,insertvalue;
node *root=new node();
root=NULL;
//root->data=NULL;
scanf("%d",&numberofnodes);
for(int i=0;i<numberofnodes;i++){
scanf("%d",&insertvalue);
//printf("A\n");
root=insert_node(root,insertvalue);
// printf("OK\n");
}
display(root);
printf("Find Successor of ?? Enter node value\n");
int key;
scanf("%d",&key);
node *successornode=new node();
if(getSuccessor(root,key)!=NULL){
successornode=getSuccessor(root,key);

printf("Successor node=%d\n",successornode->data);
}
else{

printf("No Successor Found\n");
}
return 0;
}
``````
``````struct node * inOrderSuccessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm
if( n->right != NULL )
return minValue(n->right);

// step 2 of the above algorithm
struct node *p = n->parent;
while(p != NULL && n == p->right)
{
n = p;
p = p->parent;
}
return p;
}

/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node * minValue(struct node* node) {
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return current;
}
``````