CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
Vasek
Vasek

Reputation: 464

Find the successor node in the BST after any key

I need implement method who searching next node after any arbitrary key. For example BST has keys {0, 2, 4, 6, 8}. For key 1 result must be 2 and for key 4 result must be 6.

After some research by google and SO, I implement it this way(C#-like pseudocode): 

class TreeNode
{
    int Key;
    TreeNode Left;
    TreeNode Right;
}

class Tree
{
    TreeNode Root;

    TreeNode FindNextNode(int key)
    {
        TreeNode node = Root;
        TreeNode succ = null;

        while (node != null) {

            if (key >= node.Key) {
                node = node.Right;
                continue;
            }

            succ = node;
            node = node.Left;
        }

        return succ;
    }
}

Everything seems to be good and even works, but such a simple implementation makes me think that I have missed whatsoever.

Is my implementation correct?

Upd: Picture for discussion enter image description here

Upvotes: 0

Views: 204

Answers (1)

gil.fernandes
gil.fernandes

Reputation: 14611

After looking at it for a while, the implementation looks correct in the latest version. There was this error mentioned in the comments:

`if (key >= null) {`

Also the left and right borders seem to be handled correctly. If the search key is beyond the maximum, null is returned. A search below the minimum should also return the first element in the list.

My only concern is that there is no null check for the input parameter. Perhaps some input parameter checking would make this implementation more robust.

I would also prefer not to use continue and use else instead.

Here is a version of this method in Kotlin enforcing non null search parameters and using else instead of continue:

fun next(key: Key): Key? {
    var node = root
    var succ: Node<Key, Value>? = null

    while (node != null) {
        if (key >= node.key) {
            node = node.right
        }
        else {
            succ = node
            node = node.left
        }
    }

    return succ?.key
}

Upvotes: 1

Related Questions