CODEWITHSUNDEEP
binary-search-tree
Milwaukoholic
Milwaukoholic

Reputation: 1161

ClosestKeyBefore(k) in a BST

I am trying to find the closest key to k before k is reached in a binary search tree. The more I think about it, the more I get confused as to where it could possibly be.

Formal definition of this method: Return the key of the item with the largest key less than or equal to k

At first I thought it would be the parent of k.. but after looking at BSTs its becoming very unclear to me. I need the algorithm for this. It should run in O(h) time where h is the height of the tree.

Thanks!

Upvotes: 0

Views: 112

Answers (1)

anonymous
anonymous

Reputation: 1317

I guess you could make use of recursion to remember your current best value (ie. closest so far). If value is bigger than the current node, you search the right subtree and you know your current node is the best answer IF there is nothing found in right subtree. In the search of the right subtree, you return your current best answer (less than or equal) and this answer will just propagate up.

When value is less than current node, you search the left subtree. The current node cannot be your best answer because it is greater than the value you're searching. Hence just return whatever left subtree returns.

The code would look something like this. This is just a simple example with integers and it returns -1 when no valid values are found.

public static int closestKeyBefore(Node node, int val) {
    if(node==null) return -1;

    if(node.value == val) return val;

    int retval = -1;
    if(node.value<val) { // Value is bigger than current node, search right
        retval = closestKeyBefore(node.right,val);
        if(retval==-1) { //Not found in right subtree
            retval = node.value; // Current node is the best answer. return this
        }
    }
    else { // Value is smaller than current node, search left
        retval = closestKeyBefore(node.left,val);
    }
    return retval;
}

Upvotes: 1

Related Questions