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.

17 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Replies
    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

      Delete
  4. 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.

    ReplyDelete
  5. 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;
    }
    }

    ReplyDelete
  6. 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;
    }

    ReplyDelete
    Replies
    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);

      }

      Delete
  7. 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.

    ReplyDelete
    Replies
    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;

      }

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


      //any advice?

      Delete
    3. guessing the main problem is here:

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

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

    ReplyDelete
  9. A Haskell solution: https://gist.github.com/pjrt/a3eb270101c40dce4047d14ec9bb15c2

    ReplyDelete
  10. 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

    ReplyDelete
  11. 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

    ReplyDelete