Inorder Successor in Binary Search Tree

Given a node in binary search tree say x,the in-order successor of node x is the node with the smallest value greater than node x’s value.

inorderSuccesor

In above binary search tree, in-order successor of 18 is 20, successor of 6 is 7 and successor of 13 is 15.

Algorithm : In in-order traversal of binary search tree we get number in ascending order.Hence the successor of a node will be either to the right of node(if exists) or one level above.

Method 1: (If Parent pointer is given)

The code for finding in-order successor is broken into two cases:

i) If the right subtree of node x is not empty then the successor of x is just the leftmost node in the right subtree.
ii) If the right subtree of node x is empty and x has a successor y,then y is the lowest ancestor of x whose left child is also an ancestor of x.

struct node* minValue(struct node* node)
{
    struct node* n = node;
    while(n->left!=NULL)
        n=n->left;
    return n;
}
struct node* inOrderSuccessor(struct node* root,struct node* x)
{

    if(x->right)
        return minValue(x->right);

    else
    {
        y = x->parent;
        while(y !=NULL && x == y->right)
        {
            x = y;
            y = y->parent;
        }
        return y;
    }
}

Time Complexity : O(h) where h is height of the tree,since we either follow a path up the tree or follow a path down the tree.

Method 2: (Without Parent pointer)

Steps:
i) If the right subtree of node x is not empty then the successor of x is just the leftmost node in the right subtree.(Same as step1 of above Method).
ii) If the right subtree of node x is empty then start from the root and keep doing following
a. if the root value is greater than node value then go to left subtree.
b. if the root value is less than node value then go to right subtree.
c. Stop when we reach the node.

struct node* inOrderSuccessor(struct node* root, struct node* x)
{
    if( x->right != NULL )
        return minValue(x->right);

    struct node *successor = NULL;

    while (root != NULL)
    {
        if (x->data < root->data)
        {
            successor = root;
            root = root->left;
        }
        else if (x->data > root->data)
            root = root->right;
        else
           break;
    }
    return successor;
}

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

3 Thoughts on “Inorder Successor in Binary Search Tree

  1. Anonymous on September 15, 2013 at 10:38 pm said:

    If node n is not present in the tree it should return null but it does not…should we add a check for such condition or are we assuming already that n is a part of the tree..??

  2. Hi,

    The Method 2 is incorrect.
    I considered the following tree:

    4
    2 6
    1 3 5 7

    When I pass the node for 2, I get the 4 as the successor node (should be 3).
    Similarly, when I pass in 6, I get Null as the successor node (should be 7).

    Thanks!

    • It’s correct;
      If you pass the node for 2, since node 2 has the right subtree , it falls in the first case

      if( x->right != NULL )
      return minValue(x->right);

      And the minValue of the right subtree of 2 is 3. Therefore, it will return 3.

      Same thing for the node 6.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation