Inorder Successor

A nice video for learning the data structures and algorithm.

Problem 

Find the next node of a node while traversing inorder.  i.e.

if tree is like 

               5

      2               10

1         3      9          14 

            

If we are given to find the inorder successor of 1 then it will be 2,

for 3 it would be 5 as the next element to be printed in order is 1->2->3>5>9>10>14

Algorithm

1. If right child of the node given is not null then find the minimum element in the right subtree, it will be your inorder successor.

2.  Else keep track of the ancestor= root node, ssuccessor null;
while (anc!= suc)
    - Point successor to ancestor
    - Move ancestors to left if data is lesser than ancestor node.
 
3. If data is greater then ancestor node then move ONLY ancestor to right and keep succesor to its current position.

4. Return successor if ancestor is equals to data.

C++ Code 

int inorder_suc(btptr t, int data)
{
    btptr cur=findn(t,data);
    //cout<<"\ncur="<<cur->data<<endl;
    if (cur->right != NULL)
        return (minval(cur->right));
   else {
      btptr anc=t,suc=NULL;
      while(anc != suc)
      {
        if(cur->data < anc->data)
        {
          //cout<<"left anc="<<anc->data;
          suc=anc;
          //cout<<"suc="<<suc->data;
          anc=anc->left;
        }
        else if (cur-> data > anc->data){
            anc=anc->right;
            //cout<<"\nanc="<<anc->data;
        }
        else
            return suc->data;
    }
    }
}


btptr findn(btptr t, int data)
{
    if (t!= NULL)
    {
        //cout<<"\naya="<<t->data;
        if (t->data == data)
            return t;
        if (data < t->data)
            return(findn (t->left, data));
        else
            return (findn (t->right, data));
    }
}