Monday, February 21, 2011

Inorder successor for BST


Inorder traversal:

left
root
right

Algorithm:

  1. Perform inorder traversal.
  2. Locate the required node (q) first.
  3. if 'q' found, print the next node and exit



#define TRUE 1
#define FALSE 0

void isuccessor(node *p, node *q) {
 
 // used to identify whether the given node is found
 static int is_node_found = FALSE;
 
 // if either of this are null, return
 if( !p || !q) 
  return;
 
 // left sub-tree
 isuccessor(p->left, q);
 
 // root, i.e. logic foreach node is done here
 // already q found, print this node and quit
 if( is_node_found ) {
  printf("%d", node->info);
  exit(0);
 }
 
 // we have found q
 if( q->info == p->info ) {
  is_node_found = TRUE; 
       
 } 
 
 // right sub-tree
 isuccessor(p->right, q);
}

No comments :

Post a Comment