ProAnswers.org

algorithm Predecessor of a node in a Binary Search Tree

algorithm Predecessor of a node in a Binary Search Tree

typedef struct node

	{

	    int data;

	    struct node *left, *right, *parent;

	}node;

	 

	node *tree_max(node *BSTNode){

	    while(BSTNode -> right != NULL)

	    {

	        BSTNode = BSTNode -> right;

	    }

	        return BSTNode;

	}

	 

	node *predecessor(node *Tnode){

	    node *temp;

	    if(Tnode -> left != NULL)

	        return tree_max(Tnode -> left);

	    temp = Tnode -> parent;

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

	        Tnode = temp;

	        temp = temp -> parent;

	    }

	    return temp;

	}