Finding the closest node in the tree

Problem

You are given the pointer to the binary tree and the value. You algorithm should find the pointer to the node that has the closest value to the given value.
For example, in the given tree in Figure 1.

If a 13 is given, your algorithm should return 12.

We can achieve $O( log {N})$ running time through binary search with the little tweak.
In stead of finding the exact match in the tree, we look for two closest numbers, one is smaller than the target number and the other larger than the target number.

Here is the rough algorithm

1) Given the pointers to min, max, cur, with the target, check if the cur node has the same value as the target. If so, return the current node.

2) check if the target is larger than cur node, if so, search the cur->left. Update the min pointer with the closer to the target.

3) check if the target is smaller than cur node, if so, search the cur->right. Update the max pointer with the closer to the target.

4) perform these step until, cur is empty. If we encounter empty. return the closer number to the target between min, and max nodes.

Here is the complete code running in $O( \log {N})$

	#include <iostream>
	#include <math.h>
	using namespace std;
	struct node {
	node* left;
	node* right;
	int value;
	node(int v) : value(v), left(0), right(0){}
	};
	node * find_closest(node * min, node* max, node *cur, int target)
	{
	if (!cur)
	{
	int l_diff = (!min) ? INT_MAX : abs(min->value - target);
	int r_diff = (!max) ? INT_MAX : abs(max->value - target);
	return (l_diff > r_diff) ? max : min;
	}
	node *l = min, *r = max, *next = 0;
	if (target == cur->value)
	return cur;
	else if (target < cur->value)
	{
	r = (max && max->value < cur->value) ? max : cur;
	next = cur->left;
	}
	else {
	l = (min && min->value > cur->value) ? min : cur;
	next = cur->right;
	}
	return find_closest(l, r, next, target);
	}
	int main()
	{
	node * n12 = new node(12);
	node * n5 = new node(5);
	node * n3 = new node(3);
	node * n8 = new node(8);
	node * n1 = new node(1);
	node * n4 = new node(4);
	node * n11 = new node(11);
	node * n16 = new node(16);
	node * n14 = new node(14);
	node * n20 = new node(20);
	n12->left = n5;
	n12->right = n16;
	n5->left = n3;
	n5->right = n8;
	n3->left = n1;
	n3->right = n4;
	n8->right = n11;
	n16->left = n14;
	n16->right = n20;
	node *found = find_closest(0, 0, n12, 19);
	cout << "closest to 19 in the tree =" << ((found) ? found->value : -1) << endl;
	found = find_closest(0, 0, n12, 10);
	cout << "closest to 10 in the tree =" << ((found) ? found->value : -1) << endl;
	return 1;
	}

view raw find_closest_node.cpp hosted with ❤ by GitHub

Practice Statistics

21:47: to hand-wrote the code on the paper - need to work on neater hand writing
6:33: to type the code in the node pad
6:40: to verify the code.


UPDATE(2019-07-26): solved the problem in a different way. Looking at the previous answer, I don't we need to keep both min and max value at all. We just need to keep the closest value that had been seen.

For each value we encounter, we perform the followings.

Given target value, T.

If the current node's value, V is closer than previous closet, C, set the C to V.

Case 1: If V == T, we found the exact value, stop the searching.

Case 2: If V < T, we know that all the values on the left side of V are further away than V so only search right side of V.

Case 3: if V > T, we know that all the values on the right side of V are further away than V, so only search left side of V.

Here is the solution in python

	class Node:
	def __init__(self, value):
	self.value = value
	self.left = self.right = None
	class FindClosest:
	def search(self, root, target):
	self.min = None
	self.binary_search(root, target)
	return self.min
	def binary_search(self, current, target):
	if current == None:
	return
	if self.min == None or abs(self.min - target) > abs(current.value - target):
	#replace min
	self.min = current.value
	if current.value == target:
	return
	elif current.value > target:
	self.binary_search(current.left, target)
	else:
	self.binary_search(current.right, target)
	n12 = Node(12)
	n5 = Node(5)
	n16 = Node(16)
	n3 = Node(3)
	n8 = Node(8)
	n1 = Node(1)
	n4 = Node(4)
	n11 = Node(11)
	n14 = Node(14)
	n20 = Node(12)
	n3.left = n1
	n3.right = n4
	n8.right = n11
	n5.left = n3
	n5.right = n8
	n16.left = n14
	n16.right = n20
	n12.left = n5
	n12.right = n16
	f = FindClosest()
	target = 13
	print("target = {} closest = {}".format(target, f.search(n12, target)))

view raw find_closest_number_in_binary_tree.py hosted with ❤ by GitHub

Practice statistics

7:00: come up with a binary search
6:00: to write up the code
3:00: to fix typos
5:00: to write the test code (had to find the usage of abs() method)


UPDATE(2022-05-21): solved the same problem in a non-recursive way.

8:56: to come up with an algorithm

15:00: write up the code with the error. 

3:00: to fix up the error

	class node:
	def __init__(self, value):
	self.left = None
	self.right = None
	self.value = value
	def __str__(self):
	return str(self.value)
	def find_node (root: node, target: int) -> node:
	closest = None
	cur = root
	while (cur != None):
	if cur.value == target:
	return cur
	if closest == None or (abs(closest.value - target) > abs(cur.value - target)) :
	closest = cur
	if cur.value > target:
	cur = cur.left
	elif cur.value < target:
	cur = cur.right
	return closest
	root = node(12)
	node5 = node(5)
	node16 = node(16)
	node3 = node(3)
	node8 = node(8)
	node14 = node(14)
	node20 = node(20)
	node1 = node(1)
	node4 = node(4)
	node11 = node(11)
	root.left = node5
	root.right = node16
	node5.left = node3
	node5.right = node8
	node3.left = node1
	node3.right = node4
	node8.right = node11
	node16.left = node14
	node16.right = node20
	found = find_node(root, 13)
	print("found = {}".format(found))
	found = find_node(root, 4)
	print("found 2 = {}".format(found))

view raw find_closest_node_in_binary_tree.py hosted with ❤ by GitHub