Find the nearest integer of a given number in the binary search tree.

Given a Binary Search Tree (BST) contains integers and an integer. We aim to find the nearest node to input integer in the BST. Let us understand this with an example.

We have given a binary search tree root node and a target(14) as showing in picture.

Let’s see how our solution works to get the nearest node to the target integer.

We store the diff (4) which we consider as minimum for now and difference is greater than ‘0’, we jumps to its right node.
As diff -1 which is less than 0, we have to move to its left node which is ‘NULL’ and diff is lesser than previous diff(4). So, our resultant node is ’15’.

This algorithm runs with O(H), where is ‘H’ is the height of the tree. Let’s see the code for this algorithm.

Node *getNearTarget(Node *root, int target) {
	if (root == NULL) {
		return NULL;
	}
	Node *curr = root;
	Node *targetNode = root;
	int diff = target - curr->data;
	while (curr != NULL) {
		if (diff < 0) {
			curr = curr->left;
		}
		else {
			curr = curr->right;
		}
		if (curr == NULL) {
			break;
		}
		if (abs(diff) > abs(target - curr->data)) {
			targetNode = curr;
		}
		diff = target - curr->data;
	}
	return targetNode;
}

This algorithm runs with linear complexity in worst case. Complete code for this algorithm with driver code is as follows.

// Complexity O(H) with constant space.
// Output
Node near to target 9 is: 9

I hope this helps you to understand the algorithm. If you have any better approach to solve this problem, please let our readers know by commenting below. Happy Learning!.