Find Closest Element in Binary Search Tree

Find Closest Element in Binary Search Tree

The problem of finding a closest element in a tree to a given value is another case where we can use the property of binary search tree.

Problem statement 

Given a Binary Search Tree and a value, find the closest element to the given value in BST.

Analysis

Simple approach is to go to all elements of BST and find out the difference between the given value and value of the element. Get the minimum value and add or subtract that minimum value from the given value, we would get the closest element in the BST.

Do we really need to scan all the nodes? No we don't need to.
Let's consider it case by case.
Case 1 : If the value of the node under consideration is equal to value, then our minimum difference would be zero and closest value would the value itself.

Case 2 : If the value of the node under consideration is greater than given value.
By virtue of BST, we know that nodes on the right side of the given node would be greater than this. Hence the difference between the given value and all nodes on the right side would only increase. Hence there is no element on the right side, which is closer than the node itself. Hence the right sub tree is discarded.

Case 3 : If the value of the node under consideration is less than the given value.
Again same logic applies as in case 2. Since all elements in left sub tree are less than the node, difference between given value and the nodes on left side would only increase. Hence we can safely discard the left sub tree.

Algorithm

1. Start from the root, initialize min to MAX_INT 
2. If the difference between the node and given value is less than minimum, update minimum.
3. Now, check if the given value is less than the node value, search closest element in left sub tree. Here, candidate is root till now.
4. If the given value is greater than the node value, search closest element in right sub tree. 
5. Take care while comparing minimum value and difference and storing the minimum value. We need to store minimum value with the sign.

Complete Code

void closest_element(Node *root, int value, int *min){

        if(!root)
                return ;

        int diff = abs(root->value - value);

        if(abs(*min) > abs(diff)){
                *min = diff;
        }

        if(root->value > value)
                closest_element(root->left, value, min);
        else
                closest_element(root->right, value, min);
}

Execution

This execution is for the following tree:

Enter the number: 14
Difference between node value 30 and given value 14  is :16
Difference between node value and given value is less the current min 1000 hence updating min to 16
Since node value 30 is greater than given value 14, moving to left sub tree

Difference between node value 20 and given value 14  is :6
Difference between node value and given value is less the current min 16 hence updating min to 6
Since node value 20 is greater than given value 14, moving to left sub tree

Difference between node value 10 and given value 14  is :-4
Difference between node value and given value is less the current min 6 hence updating min to 4
Since node value 10 is less than given value 14, moving to right sub tree

Difference between node value 12 and given value 14  is :-2
Difference between node value and given value is less the current min 4 hence updating min to 2
Since node value 12 is less than given value 14, moving to right sub tree

Closest Element is 12

Complexity analysis

Average complexity of this algorithm is O(logN), but if the tree is completely skewed, i.e worst case complexity would be O(N).