How to find the closest element to a given key value in a binary search tree?

Question

Given a bst with integer values as keys how do I find the closest node to that key in a bst ? The BST is represented using a object of nodes (Java). Closest will be for eg 4,5,9 and if the key is 6 it will return 5 ..

Answer 1

Traverse the tree as you would to find the element. While you do that record the value that is closest to your key. Now when you didn't find a node for the key itself return the recorded value.

So if you were looking for the key 3 in the following tree you would end up on the node 6 without finding a match but your recorded value would be 2 since this was the closest key of all nodes that you had traversed (2,7,6).

                 2
              1      7
                   6   8

Answer 2

Here's a recursive solution in Python:

def searchForClosestNodeHelper(root, val, closestNode):
    if root is None:
        return closestNode

    if root.val == val:
        return root

    if closestNode is None or abs(root.val - val) < abs(closestNode.val - val):
        closestNode = root

    if val < root.val:
        return searchForClosestNodeHelper(root.left, val, closestNode)
    else:
        return searchForClosestNodeHelper(root.right, val, closestNode)

def searchForClosestNode(root, val):
    return searchForClosestNodeHelper(root, val, None)

Answer 3

Traverse takes O(n) time. Can we proceed it in top-bottom? like this recursive code:

Tnode * closestBST(Tnode * root, int val){
    if(root->val == val)
        return root;
    if(val < root->val){
        if(!root->left)
            return root;
        Tnode * p = closestBST(root->left, val);
        return abs(p->val-val) > abs(root->val-val) ? root : p;
    }else{
        if(!root->right)
            return root;
        Tnode * p = closestBST(root->right, val);
        return abs(p->val-val) > abs(root->val-val) ? root : p;
    }   
    return null;
}