Closest element in binary search tree

Closest element in a binary search tree

The problem statement is: given a binary search tree and a value, find the closest element to that value in the binary search tree. For example, if below is the binary search tree and value given is 16, then the function should return 15.

closest element in binary search tree
Closest element in a binary search tree

Closest element in BST: thoughts

A simple approach is to go to all nodes of BST and find out the difference between the given value and value of the node. Get the minimum absolute value and add that minimum value from the given value, we would get the closest element in the BST.

Do we really need to scan all the nodes? No we don’t need to. Let’s say given value is k.

What if current.value is equal to the k? That means it is the closest node to the k and we cannot go better than this. Return the node value as closest value.

If current.value is greater than k, by virtue of BST, we know that nodes on the right subtree of the current node would be greater than the current.value. Hence the difference between k and all the nodes on the right subtree would only increase. So, there is no node on the right side, which is closer than the current node itself. Hence, the right subtree is discarded. If there is no left subtree, return current.value.

If current.value is less than k,  with the same logic above, all elements in left subtree are less than the value of current.value, the difference between k and the nodes on left subtree would only increase. So, we can safely discard the left subtree. If there is no right subtree, return current.value.

When we return the closest element from left subtree, we check if the difference between current.value and k less than difference between returned value and k. If it is less, then return current.value else return the returned value from the subtree.

Closest element in a binary search tree: algorithm

  1. If k == current.value, return current.value.
  2. If k < current.value, search the closest element in left subtree including the root as current is still a candidate.
    1. Return current.value if there is no left subtree.
  3. If k > current.value, search the closest element in the right subtree.
    1. Return current.value if there is no right subtree.
  4. If abs(current.value - k ) < abs(returnedValue - k ), return current.value else return returnedValue

Closest element in binary search tree: implementation

package com.company.BST;

/**
 * Created by sangar on 3.11.18.
 */
public class ClosestElement {

    public int findClosest(TreeNode node, int k){
        if(node == null) return -1;

        int currentValue = (int)node.getValue();

        if(currentValue == k) return currentValue;

        if(currentValue > k){
            if(node.getLeft() == null) return currentValue;

            //Find closest on left subtree
            int closest = findClosest(node.getLeft(), k);
            if(Math.abs(closest - k) > Math.abs(currentValue - k)){
                return currentValue;
            }
            return closest;
        }
        else {
            if (node.getRight() == null) return currentValue;

            //Find closest on right subtree
            int closest = findClosest(node.getRight(), k);
            if (Math.abs(closest - k) 
				> Math.abs(currentValue - k)) {
                return currentValue;
            }
            return closest;
        }
    }
}
package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}

package test;

import com.company.BST.BinarySearchTree;
import com.company.BST.ClosestElement;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class ClosestElementTest {

    ClosestElement tester = new ClosestElement();

    @Test
    public void closestElementTest() {

        BinarySearchTree<Integer> binarySearchTree =
						new BinarySearchTree<>();
        binarySearchTree.insert(10);
        binarySearchTree.insert(8);
        binarySearchTree.insert(15);
        binarySearchTree.insert(12);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);

        assertEquals(6,
			tester.findClosest(binarySearchTree.getRoot(),1));
    }
}

Complexity of algorithm to find closest element in a binary search tree is O(n) if tree is completely skewed.

Please share if there is something wrong or missing. If you are preparing for interviews, please signup for free interview material.