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})$


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

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