top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

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

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
First comes the left sub tree then root node and right subtree
@Farheen: Can you share the sample code?

2 Answers

+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;
}
answer Jul 12, 2016 by Shivam Kumar Pandey
0 votes
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;
}
answer May 17, 2016 by Rajan Paswan
Similar Questions
+1 vote

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

+4 votes

How to convert a binary tree into binary search tree keeping the structure of tree intact?

+2 votes

How to find the smallest element in a Binary Tree (Not BST)? Sample C/C++ code would be helpful.

...