ProAnswers.org

algorithm Successor of a node in a Binary Search Tree

algorithm Successor of a node in a Binary Search Tree

typedef struct node

	{

	    int data;

	    struct node *left, *right, *parent;

	}node;

	 

	node *tree_min(node *BSTNode){

	    while(BSTNode -> left != NULL){

	        BSTNode = BSTNode -> left;

	    }

	        return BSTNode;

	}

	 

	node *successor(node *Tnode){

	    node *temp;

	    if(Tnode -> right != NULL)

	        return tree_min(Tnode -> right);

	    temp = Tnode -> parent;

	    while(temp != NULL && Tnode  = temp -> right){

	        Tnode = temp;

	        temp = temp -> parent;

	    }

	    return temp;

	}