**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

ReplyDeleteCould 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

ReplyDelete