# Given a value v, in a BST find the next value in order.

Since it's the BST, so we could find the given value very fast,

a) if the given value has right-children:
 then go down to it's right-children subtree--> find the smallest one, by go left->left->
b) if the given value do not has the right children:
 the the next node should be it's parent, so we can keep trace about it's parent

so combine these we can check

if (current->left == givenV)
{
    targetNode = current->left;
    if (targetNode->right !=NULL) return searchMin(targetNode->right);
    return current;
}

if (current->right == givenV)
{
    targetNode = current->right ;
    if (targetNode->right !=NULL) return searchMin(targetNode->right);
    ===> this part will be much more complex;
}

a easy way is to do the inorder traversal , but compare the value with the given value, and whenever it larger than the given value, we have found it.

void InorderTraverNextNode(node * root, int givenValue, node * returnNode)
{
   if (root ==NULL) return;
   InorderTraverNextNode(root->left, givenValue, returnNode );
   if (root->value > givenValue)
       {
           cout <<"The founded next value is: " + char(root->value) << endl;
           returnNode = root;
           return;
        }
   InorderTraverNextNode(root->right, givenValue, returnNode );
}

If this is not BST, I think we can still do this, but simply make a counter, or a flag, but put that flag, such as when found the given key, make the flag = True, and if the flag is true, (when continuing traver...), the next round we've already found the results.

void InorderTraverNextNode(node * root, int givenValue, bool flag, node * returnNode)
{
   if (root ==NULL) return;
   InorderTraverNextNode(root->left, givenValue, flag, returnNode );
   
   if (flag ==True)
       { 
           cout <<"The founded next value is: " +  char(root->value) << endl;
           returnNode = root;
           return; 
       }
   if (root->value == givenValue)
       {
           flag = True;
       }           

    InorderTraverNextNode(root->right, givenValue, flag, returnNode );
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥