Algorithm for successor

I need an algorithm for returning the successor node of some arbit开发者_如何学Crary node of the given binary search tree.

To give you an answer with the same level of detail as your question: Go up until going right is possible, and then left until you reach a leaf.

There are two general approaches:

• If your binary tree nodes have pointers to their parent node, then you can traverse directly from the node to the successor node. You will have to determine how to use the parent pointers to do the traversal.
• If your binary tree nodes do not have parent pointers, then you will have to do an inorder traversal of the tree starting at the root (presumably you have a root node pointer) and return the next node after the given node.

You need to maintain a zipper as you descend the tree. A zipper is simply a list of the nodes you have traversed, and for each an indication of whether you next went left or right. It allows you to travel back up in the tree even if there aren't any pointers from children to parents.

The algorithm for successor is to go back (up in the zipper) as long as you were coming from the left, then go right once, and then descend to the leftmost child.

It's easier with a figure...

The successor of a node implies you are looking for an inorder successor. The following method helps you determine the inorder successor WITHOUT ANY PARENT NODE OR EXTRA SPACE NON-RECURSIVELY

struct node * inOrderSuccessor(struct node *root, struct node *n)
   { 
   //*If the node has a right child, return the smallest value of the right sub tree*

   if( n->right != NULL ) 
      return minValue(n->right); 

   //*Return the first ancestor in whose left subtree, node n lies*
   struct node *succ=NULL;
   while(root) 
   { 
      if(n->datadata < root->data) 
         {
            succ=root; root=root->left; 
         }

      else if(n->data > root->data) 
         root=root->right; 
      else break; 
   } 
  return succ;
 }

I'm quite certain this is right. Do correct me if I am wrong. Thanks.