text: Inorder Successor in Binary Search Tree |  ; A binary tree node has data , the pointer to left child and a pointer to right child ; Give a binary search tree and a number , inserts a new node with the given number in the correct place in the tree . Returns the new root pointer which the caller should then use ( the standard trick to avoid using reference parameters ) . ; 1. If the tree is empty , return a new , single node ; 2. Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; step 1 of the above algorithm ; step 2 of the above algorithm ; 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 . ; loop down to find the leftmost leaf ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Driver program to test above functions
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left ; struct node * right ; struct node * parent ; } ; struct node * minValue ( struct node * node ) ; struct node * insert ( struct node * node , int data ) { if ( node == NULL ) return ( newNode ( data ) ) ; else { struct node * temp ; if ( data <= node -> data ) { temp = insert ( node -> left , data ) ; node -> left = temp ; temp -> parent = node ; } else { temp = insert ( node -> right , data ) ; node -> right = temp ; temp -> parent = node ; } return node ; } } struct node * inOrderSuccessor ( struct node * root , struct node * n ) { if ( n -> right != NULL ) return minValue ( n -> right ) ; struct node * p = n -> parent ; while ( p != NULL && n == p -> right ) { n = p ; p = p -> parent ; } return p ; } struct node * minValue ( struct node * node ) { struct node * current = node ; while ( current -> left != NULL ) { current = current -> left ; } return current ; } struct node * newNode ( int data ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> data = data ; node -> left = NULL ; node -> right = NULL ; node -> parent = NULL ; return ( node ) ; } int main ( ) { struct node * root = NULL , * temp , * succ , * min ; root = insert ( root , 20 ) ; root = insert ( root , 8 ) ; root = insert ( root , 22 ) ; root = insert ( root , 4 ) ; root = insert ( root , 12 ) ; root = insert ( root , 10 ) ; root = insert ( root , 14 ) ; temp = root -> left -> right -> right ; succ = inOrderSuccessor ( root , temp ) ; if ( succ != NULL ) printf ( " Inorder Successor of % d is % d " , temp -> data , succ -> data ) ; else printf ( " Inorder Successor doesn ' exit " getchar ( ) ; return 0 ; }