## Saturday, March 2, 2013

### No. 45 - Closest Node in a Binary Search Tree

Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

For instance, in the binary search tree in Figure 1, the node closest to 29 is the node with value 28.
 Figure 1: A sample binary search tree, in which the closest node to 29 is the node with value 28

Analysis: Let’s analyze this problem step by step, taking the binary search in Figure 1 and 29 as an example.
We start from the root node with value 32, and the distance to 29 is 3. Since the value 32 is greater than 29, and all values in the right sub-tree are greater than 32, distances to 29 in the right sub-tree should be greater than 3. We move to the left sub-tree.
The next node to be visited contains value 24, and the distance to 29 is 5. Since 5 is greater than the previous closest distance 3, the closest node up to now remains the node with value 32. Additionally, the current value 24 is less than 29, and all values in the left sub-tree are less than 24, so distances to 29 in the left sub-tree will be greater than 5. We move on to visit the right sub-tree.
The next node to be visited contains value 28, and the distance to 29 is 1. Since 1 is less than the previous closest distance 3, the closest node is updated to the node with value 28. Additionally, the value 28 is less than 29, and all values in the left sub-tree areless than 28, so distances to 29 in the left sub-tree will be greater than 1. Let’s continue to visit the right sub-tree.
Finally we reach a left node with value 31. The distance to 29 is 2 and it is greater than the previous closest distance 1, so the closest node to 29 is still the node with value 28.
According to the step-by-step analysis above, we could implement the following code:
BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
BinaryTreeNode* pClosest = NULL;
int minDistance = 0x7FFFFFFF;
BinaryTreeNode* pNode = pRoot;
while(pNode != NULL)
{
int distance = abs(pNode->m_nValue - value);
if(distance < minDistance)
{
minDistance = distance;
pClosest = pNode;
}

if(distance == 0)
break;

if(pNode->m_nValue > value)
pNode = pNode->m_pLeft;
else if(pNode->m_nValue < value)
pNode = pNode->m_pRight;
}

return pClosest;
}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

1. This comment has been removed by the author.

2. This comment has been removed by the author.

1. Salemetsiz Be,

11/10!! Your blog is such a complete read. I like your approach with #topic. Clearly, you wrote it to make learning a cake walk for me.

I like the support for S3 in the AWS console, especially being able to apply ACLs at time of upload. However, it would be very good if the view was sortable by last modified date, as I am typically working with the last 10-15 files uploaded.

It was cool to see your AWS Tutorial USA article pop up in my google search for the process yesterday. Great Guide.
Keep up the good work!

Cheers,

ganesh

3. Could we create two integers as "nodeSmall" & "nodeLarge" to keep track of the two closest values. Using this, the code doesn't need to compare "distance < minDistance" for each node.

4. struct node*nearest(struct node*root,int k)
{
if(root == NULL)
return NULL;
else if(root->data == k)
return root;
else if(root->data>k)
{
struct node*z = nearest(root->left,k);
if(z!=NULL)
{
if(abs(z->data-k)>abs(root->data-k))
return root;
else
return z;
}
else
return root;
}
else
{
struct node*z = nearest(root->right,k);
if(z!=NULL)
{
if(abs(z->data-k)>abs(root->data-k))
return root;
else
return z;
}
else
return root;
}
}

5. A Java solution:

Node findClosestNodeToTargetValue(Node root, int target) {

if (root == null) return null;

Node closestNode = root;
int closestDiff = Integer.MIN_VALUE;

while(root != null) {
··if (root.data == target) return root;
··
··int diff = Math.abs( data - root.data);
··if (diff < closestDiff) {
···closestDiff = diff;
···closestNode = root;
··}
··root = (target > root.data) ? root.getRight() : root.getLeft();
}

return root;
}

1. int mostClosetNode(Node root, int value)
{
int min = Integer.MAX_VALUE;
int mostClosestNode = mostClosetNodeUtil(root,value,min);
return mostClosestNode;
}

int mostClosetNodeUtil(Node root, int value,int min)
{
if(root==null)
{
return Integer.MAX_VALUE;
}

int currDiff = Math.abs(root.data - value);
if(currDiff<min)
{
min = currDiff;
return root.data;
}

int minLeft = mostClosetNodeUtil(root.left,value,min);
int minRight = mostClosetNodeUtil(root.right,value,min);
return Math.min(minLeft,minRight);

}

6. how much better can we do this using recursion.

Can someone tell me the recursion approach and compare the memory and efficiency between the two approaches.

1. //recursive solution: way more elegant.

private static Node ClosestNode(Node node, int value)
{
if (node == null)
return null;

if (value != node.Key)
{
var closestNode = value < node.Key ? ClosestNode(node.Left, value) : ClosestNode(node.Right, value);
if (closestNode != null)
{
if (Math.Abs(closestNode.Key - value) < Math.Abs(node.Key - value))
return closestNode;
return node;
}
return node;
}
return node;

}

2. //i'm looking for a node equal or larger then an input so i tryed to modifiy the code with no luck

private T Search4(Node tmp, T searchItem)
{
if (tmp == null) return default(T);
if (searchItem.CompareTo(tmp.data) == 0)
{
return tmp.data;
}
var closestNode = (searchItem.CompareTo(tmp.data) < 0 ? Search4(tmp.left, searchItem) : Search4(tmp.right, searchItem));
if (closestNode != null)
{
if ((searchItem.CompareTo(tmp.data) > (searchItem.CompareTo(closestNode))))
{
return closestNode;
}
return tmp.data;
}
return tmp.data;

3. guessing the main problem is here:

var closestNode = (searchItem.CompareTo(tmp.data) < 0 ?

7. Can you explain how this would be different in C# using generics?

9. Hi Man,

Best thing I have read in a while on this No. 45 - Closest Node in a Binary Search Tree . There should be a standing ovation button. This is a great piece.

I am new to Amazon S3, and so far it seems to be working fine, but I do have one quick question:

To upload my files, I just go to Amazon's Console - within my Firefox Browser; but I am wondering:
After the Upload is started, is it OK to Exit Firefox right then . . . OR does the upload work better if I keep Firefox running? AWS Tutorial

Anyways great write up, your efforts are much appreciated.

Grazie,
Ajeeth

10. Hola,

Interesting piece!Great to see someone write No. 45 - Closest Node in a Binary Search Tree who is not a fanatic or a complete skeptic.

I'm new to AWS and I am using it to work on my senior thesis project in college. The project requires using Microsoft SQL however I am using a mac, so I figured the easiest way to make this work would be to use AWS. I am trying to use only options that are eligible for the free tier since my budget is not a lot. AWS Tutorial

Please keep providing such valuable information.

,Merci
Ajeeth

11. I have been searching for a useful post like this on salesforce course details, it is highly helpful for me and I have a great experience with this Salesforce Training who are providing certification and job assistance. Salesforce training Noida

12. With special privileges and services, UEFA BET offers opportunities for small capitalists. Together ufa with the best websites that collect the most games With a minimum deposit starting from just 100 baht, you are ready to enjoy the fun with a complete range of betting that is available within the website

ufabet , our one another option We are a direct website, not through an agent, where customers can have great confidence without deception The best of online betting sites is that our Ufa will give you the best price