**Given a binary search tree and a value**

__Problem:__*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 |

**Let’s analyze this problem step by step, taking the binary search in Figure 1 and 29 as an example.**

__Analysis:__
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.

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteSuper

ReplyDeleteSalemetsiz Be,

Delete11/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

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.

ReplyDeletestruct node*nearest(struct node*root,int k)

ReplyDelete{

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;

}

}

A Java solution:

ReplyDeleteNode 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;

}

how much better can we do this using recursion.

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

//recursive solution: way more elegant.

Deleteprivate 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;

}

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

Deleteprivate 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;

//any advice?

guessing the main problem is here:

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

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

ReplyDeleteA Haskell solution: https://gist.github.com/pjrt/a3eb270101c40dce4047d14ec9bb15c2

ReplyDeleteHi Man,

ReplyDeleteBest 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

Hola,

ReplyDeleteInteresting 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