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

Question

How to balance the binary search tree in C/C++? Please provide the necessary explanation also?

Answer 1

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;
}

Answer 2

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;
}