Skip to content

Instantly share code, notes, and snippets.

@jearl4
Created February 20, 2021 17:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jearl4/221c42e696bb3fca6d0a17abeb0c70cd to your computer and use it in GitHub Desktop.
Save jearl4/221c42e696bb3fca6d0a17abeb0c70cd to your computer and use it in GitHub Desktop.
Find closest value in BST
import java.util.*;
class Program {
public static int findClosestValueInBst(BST tree, int target) {
return findClosestValueInBst(tree, target, tree.value);
}
public static int findClosestValueInBst(BST tree, int target, int closest){
// find current and next value
int currentValue = Math.abs(target - closest);
int potentialValue = Math.abs(target - tree.value);
// set this if closer node is found while searching tree
if(currentValue > potentialValue){
closest = tree.value;
}
// move left or right in tree if safe
if(target < tree.value && tree.left != null){
return findClosestValueInBst(tree.left, target, closest);
}else if(target > tree.value && tree.right != null){
return findClosestValueInBst(tree.right, target, closest);
}else{
// base case, tree cant be navigated further
return closest;
}
}
static class BST {
public int value;
public BST left;
public BST right;
public BST(int value) {
this.value = value;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment