How to find the closest element to a given key value in a binary search tree?

Question

Given a bst with integer values as keys how do I find the closest node to that key in a bst ? The BST is represented using a object of nodes (Java). Closest will be for eg 4,5,9 and if the key is 6 it will return 5 ..

Bassarisk

The question appears incomplete. How is the BST stored? What do they mean by "closest" value? Smallest delta? How should ties be treated? – Afroasian

@Andrew White, how does it matter how the BST is stored? – Psyche

@Psyche It doesn't; My brain was dead that day. – Afroasian

Answer 1

Traverse the tree as you would to find the element. While you do that record the value that is closest to your key. Now when you didn't find a node for the key itself return the recorded value.

So if you were looking for the key 3 in the following tree you would end up on the node 6 without finding a match but your recorded value would be 2 since this was the closest key of all nodes that you had traversed (2,7,6).

                 2
              1      7
                   6   8

Epicurus

Answer 2

Here's a recursive solution in Python:

def searchForClosestNodeHelper(root, val, closestNode):
    if root is None:
        return closestNode

    if root.val == val:
        return root

    if closestNode is None or abs(root.val - val) < abs(closestNode.val - val):
        closestNode = root

    if val < root.val:
        return searchForClosestNodeHelper(root.left, val, closestNode)
    else:
        return searchForClosestNodeHelper(root.right, val, closestNode)

def searchForClosestNode(root, val):
    return searchForClosestNodeHelper(root, val, None)

Pulitzer

Answer 3

Traverse takes O(n) time. Can we proceed it in top-bottom? like this recursive code:

Tnode * closestBST(Tnode * root, int val){
    if(root->val == val)
        return root;
    if(val < root->val){
        if(!root->left)
            return root;
        Tnode * p = closestBST(root->left, val);
        return abs(p->val-val) > abs(root->val-val) ? root : p;
    }else{
        if(!root->right)
            return root;
        Tnode * p = closestBST(root->right, val);
        return abs(p->val-val) > abs(root->val-val) ? root : p;
    }   
    return null;
}

Cosy

The function can return null. If p = null, p->val is invalid. In fact, the last line "return null" is unreachable. – Newmodel

This appears to actually be O(h) where h is the height of the BST vs O(n) – Gusman

Answer 4

It can be solved in O(log*n*) time.

• If the value in a node is same as the given value, it's the closest node;
• If the value in a node is greater than the given value, move to the left child;
• If the value in a node is less than the given value, move to the right child.

The algorithm can be implemented with the following C++ 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;
}

You may visit my blog for more details.

Enhance

Agreed, this iterative solution will run on average O(log(n)) time and O(1) space, with worst case O(n) time and O(1) space. The recursive solution would be O(log(n) time and O(log(n)) space which is why the iterative solution is nice as it takes up less space from avoiding adding recursive calls to the call stack. – Maneating

Answer 5

The problem with the approach "left right traversal and finding the closest" is that it depends over the sequence in which elements were entered to create BST. If we search 11 for the BST sequence 22, 15, 16, 6,14,3,1,90, the above method will return 15 while the correct answer is 14. The only method should be using recursion to traverse all the nodes, returning the closest one as the result of the recursive function. This'll give us the closest value

Centri

That is simply not true. Teng Teng's answer above: https://mcmap.net/q/628839/-how-to-find-the-closest-element-to-a-given-key-value-in-a-binary-search-tree will work for the case you described, and does not traverse every node in the tree. – Inexpugnable

Answer 6

This can be done using a Queue and a ArrayList. Queue will be used to perform a breadth first search on the tree. ArrayList will be used to store the element of the tree in breadth first order. Here is the code to implement the same

Queue queue = new LinkedList();
ArrayList list = new ArrayList();
int i =0;
public Node findNextRightNode(Node root,int key)
{
    System.out.print("The breadth first search on Tree : \t");      
    if(root == null)
        return null;

    queue.clear();
    queue.add(root);

    while(!queue.isEmpty() )
    {
        Node node = (Node)queue.remove();
        System.out.print(node.data + " ");
        list.add(node);
        if(node.left != null) queue.add(node.left);
        if(node.right !=null) queue.add(node.right);            
    }

    Iterator iter = list.iterator();
    while(iter.hasNext())
        {
            if(((Node)iter.next()).data == key)
            {
                return ((Node)iter.next());
            }               
        }

    return null;
}

Sprang

Answer 7

void closestNode(Node root, int k , Node result) {
    if(root == null) 
    {
       return;      //currently result is null , so it  will be the result
    }
    if(result == null || Math.abs(root.data - k) < Math.abs(result.data - k) )
    {
      result == root;
    }
    if(k < root.data)
    {
    closestNode(root.left, k, result)
    } 
    else 
    {
        closestNode(root.right, k, result);
    }

}

Alephnull

Answer 8

Below one works with different samples which I have.

public Node findNearest(Node root, int k) {
    if (root == null) {
        return null;
    }
    int minDiff = 0;
    Node minAt = root;
    minDiff = Math.abs(k - root.data);

    while (root != null) {
        if (k == root.data) {
            return root;
        }
        if (k < root.data) {
            minAt = updateMin(root, k, minDiff, minAt);
            root = root.left;
        } else if (k > root.data) {
            minAt = updateMin(root, k, minDiff, minAt);
            root = root.right;
        }

    }
    return minAt;
}

private Node updateMin(Node root, int k, int minDiff, Node minAt) {
    int curDif;
    curDif = Math.abs(k - root.data);
    if (curDif < minDiff) {
        minAt = root;
    }
    return minAt;
}

Homophonic

Answer 9

Here is the full Java code to find the closest element in a BST.

        package binarytree;

        class BSTNode {
            BSTNode left,right;
            int data;

            public BSTNode(int data) {
                this.data = data;
                this.left = this.right = null;
            }
        }

        class BST {
            BSTNode root;

            public static BST createBST() {
                BST bst = new BST();
                bst.root = new BSTNode(9);
                bst.root.left = new BSTNode(4);
                bst.root.right = new BSTNode(17);

                bst.root.left.left = new BSTNode(3);
                bst.root.left.right= new BSTNode(6);

                bst.root.left.right.left= new BSTNode(5);
                bst.root.left.right.right= new BSTNode(7);

                bst.root.right.right = new BSTNode(22);
                bst.root.right.right.left = new BSTNode(20);

                return bst;
            }
        }

        public class ClosestElementInBST {
            public static void main(String[] args) {
                BST bst = BST.createBST();
                int target = 18;
                BSTNode currentClosest = null;
                BSTNode closestNode = findClosestElement(bst.root, target, currentClosest);

                if(closestNode != null) {
                    System.out.println("Found closest node: " + closestNode.data);
                }
                else {
                    System.out.println("Couldn't find closest node.");
                }
            }

            private static BSTNode findClosestElement(BSTNode node, int target, BSTNode currentClosest) {
                if(node == null) return currentClosest;

                if(currentClosest == null || 
                        (currentClosest != null && (Math.abs(currentClosest.data - target) > Math.abs(node.data - target)))) {
                    currentClosest = node;
                }

               if(node.data == target) return node;

                else if(target < node.data) {
                    return findClosestElement(node.left, target, currentClosest);
                }

                else { //target > node.data
                    currentClosest = node;
                    return findClosestElement(node.right, target, currentClosest);
                }
            }

        }

Decastro

Answer 10

Here is the working solution in java which uses the characteristics of BST and additional integer to store minimum difference

public class ClosestValueBinaryTree {
        static int closestValue;

        public static void closestValueBST(Node22 node, int target) {
            if (node == null) {
                return;
            }
            if (node.data - target == 0) {
                closestValue = node.data;
                return;
            }
            if (Math.abs(node.data - target) < Math.abs(closestValue - target)) {
                closestValue = node.data;
            }
            if (node.data - target < 0) {
                closestValueBST(node.right, target);
            } else {
                closestValueBST(node.left, target);
            }
        }
    }

Run time complexity - O(logN)

Space time complexity - O(1)

Moussorgsky