1
$\begingroup$

This is the problem that I have to solve:

given a node in a binary search tree, find the node with the smallest key that is greater than the key of the given node..

The algorithm that is often given is this one:

bst_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x = y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

(you can find further explanations of the problem here.)

Now, I was wondering if this can be another solution:

bst_successor(x)
    {
            if(x == NULL)
                    return NULL;
            if(x.right != NULL)
                    return abr_min(x.right)
            y = x.p;
            while(y != NULL && y.key < x.key)
            {
                    y = y.p;
            }
            return y;
    }
$\endgroup$
4
  • 4
    $\begingroup$ Your answer is missing a lot of context. What is the successor function trying to accomplish? What data structure is in the background? $\endgroup$ May 4 '20 at 21:05
  • $\begingroup$ (Answer should have been question in my preceding comment.) $\endgroup$ May 4 '20 at 21:48
  • $\begingroup$ This is the problem I have to solve: "given a node in a binary search tree, find the node with the smallest key that is greater than the key of the given node.". [Here][1], there is another explanation of my problem [1]: geeksforgeeks.org/inorder-successor-in-binary-search-tree $\endgroup$
    – Shyvert
    May 5 '20 at 8:13
  • 1
    $\begingroup$ Don't answer in the comments. Instead, update your question to include all necessary information. Don't add an "EDIT" section. Instead, just rewrite your question so that it looks whole, but now contains all the requisite information. $\endgroup$ May 5 '20 at 8:15
1
$\begingroup$

Your code is correct if the key of one node is never equal to the key of a different node.

Otherwise, you code fails to return the correct inorder-successor of the node at the bottom of the following graph.

enter image description here

$\endgroup$
1
  • $\begingroup$ There is one kind of most common errors in programming, off-by-one error and equality-neglected error. $\endgroup$
    – John L.
    May 5 '20 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.