life is fun

Inorder Successor in Binary Search Tree


Parent pointer is needed in this algorithm.
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.

Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.

1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then start from root and us search like technique. Do following.
Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise go to left side.

struct node * inOrderSuccessor(struct node *root, struct node *n)
    // step 1 of the above algorithm
    if( n->right != NULL )
        return minValue(n->right);
    struct node *succ = NULL;
    // Start from root and search for successor down the tree
    while (root != NULL)
        if (n->data < root->data)
            succ = root;
            root = root->left;
        else if (n->data > root->data)
            root = root->right;
    return succ;

Time Complexity: O(h) where h is height of tree.


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s