find inorder successor in BST without using any extra space

Question

I am looking a way to find out inorder successor of a node in BST withut using extra space.

Answer 1

To get the inorder successor of a given node N we use the following rules:

• If N has a right child R then the inorderSuccessor(N) is the leftmost decedent of R.
• Else inorderSuccessor(N) is the closest ancestor, M, of N (if it exists) such that N is descended from the left child of M. If there is no such ancestor, inorderSucessor does not exist.

Consider a sample tree:

     A
    / \
   B   C
  / \ 
 D   E
    /
   F

Whose inorder traversal gives: D B F E A C

inorderSuccessor(A) = C as C is the leftmost decedent of the right child of A.

inorderSuccessor(B) = F as F is the leftmost decedent of the right child of B.

inorderSuccessor(C) = Does not exist.

inorderSuccessor(D) = B as B is the left child of D.

inorderSuccessor(E) = A. E does not have a right child so we have scenario 2. We go to parent of E which is B, but E is right decedent of B, so we move to parent of B which is A and B is left decedent of A so A is the answer.

inorderSuccessor(F) = E as F is the left child of E.

Procedure:

treeNodePtr inorderSucessor(treeNodePtr N) {
        if(N) {
                treeNodePtr tmp;
                // CASE 1: right child of N exists.
                if(N->right) {
                        tmp = N->right;
                        // find leftmost node.
                        while(tmp->left) {
                                tmp = tmp->left;
                        }
                // CASE 2: No right child.
                } else {
                        // keep climbing till you find a parent such that
                        // node is the left decedent of it.
                        while((tmp = N->parent)) {
                                if(tmp->left == N) {
                                        break;
                                }
                                N = tmp;
                        }
                }
                return tmp;
        }
        // No IOS.
        return NULL;
}

Code In Action

Answer 2

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.