Find closest node in binary search tree

Closest node in binary search tree

Problem to find a closest node to a given value in binary search tree is another case where BST property can be used. BST property states that all nodes on left side of a node are less and on right side of node are greater than it. Problem statement goes like: given a BST and value, find closest node in binary search tree.

First and Simple approach is to go through all nodes of BST and find difference between given value and node value. Get minimum value and add or subtract that minimum value from given value to get closest node in BST. Do we really need to scan all nodes? No, we don’t. 
Let’s consider it case by case.

Case 1 : If currentNode value is equal to given value.
Then difference would be zero and closest node would currentNode.

Case 2 : If currentNode value is greater than given value.
By virtue of BST, nodes on right side of currentNode will be definitely greater than currentNode. Hence difference between given value and all nodes on right side of currentNode will only increase. Hence, there is no node in right subtree, which is closer than the currentNode itself and right sub tree is discarded.

Case 3 : If currentNode value is less than given value.
Since all nodes in left subtree are less than currentNode, difference between given value and nodes in left subtree would only increase. So left subtree can safely be discarded.

Well at each node, discard either left or right subtree of node. Typical case of divide and conquer. Also, what process we are doing on entire tree, needs to be done on subtree. There comes recursion.

Algorithm to find closest node in binary search tree

1. Start from root, initialize min to MAX_INT.
2. If currentNode value is equal to given value, return currentNode.
3. If difference between currentNode and given value is less than minimum,  update minimum 
3. Check if given value is less than currentNode value
   3.1 search closest node in left subtree.
4. If given value is greater than currentNode value, 
   4.1 search closest node in right subtree. 

Take care while comparing minimum value and difference and storing minimum value. We need to store minimum value with sign
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
#define true 1
#define false 0
 
void findClosestNode(Node *root, int value, int *min){
	if(!root)
		return;
 
	int diff = root->value - value;
 
	if(abs(*min) > abs(diff)){
		*min = diff;
	}
	/* Case 2 : Look for in left subtree */
 
	if(root->value > value)
		findClosestNode(root->left, value, min);
	else
	/* Case 3 : Look for in right subtree */ 
		findClosestNode(root->right, value, min);
}
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
 
Node *addNode(Node *node, int value){
	if(!node) return createNode(value);
	
        if (node->value > value)
	    node->left = addNode(node->left, value);
	else
            node->right = addNode(node->right, value);

	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	int min = 99999;
	int value  = 27;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
 
	inorderTraversal(root);	
	findClosestNode( root, value, &min);
 
	printf("\nClosest node for %d is : %d", value, value + min );
	return 0;
}

Execution for below tree would be :

closest node in binary search tree

Processing node : 30 Difference : 3
Processing node : 20 Difference : 3
Processing node : 25 Difference : -2

Closest node for 27 is : 25

Average complexity of this algorithm to find closest node in binary search tree is O(logN), but if the tree is completely skewed, i.e worst case complexity will be O(N).

Please share if there is something wrong or missing. If you want to contribute to website or have an interview experience to share, please contact us.

  • Dmitry

    For the BST 30 20 21 40 31 and value 29 the result of your algorithm will be 21 but the correct one is 31

    • http://algorithmsandme.in/ Jitendra Sangar

      Let me check and I will get back to you! Thanks for pointing out anyways.

    • http://algorithmsandme.in/ Jitendra Sangar

      I checked, correct answer in this case should be 30. And algorithm give that. Please follow this link to execute it yourself.

      http://ideone.com/Ynj9eh