Find Closest Value In BST

Code

Python

def findClosestValueInBst(tree, target):
return findClosestValueInBstHelper(tree, target, float("inf"))
​
​
def findClosestValueInBstHelper(tree, target, closest):
if tree is None:
return closest
if abs(target - closest) > abs(target - tree.value):
closest = tree.value
if target < tree.value:
return findClosestValueInBstHelper(tree.left, target, closest)
elif target > tree.value:
return findClosestValueInBstHelper(tree.right, target, closest)
else:
return closest

JavaScript

function findClosestValueInBst(tree, target) {
return findClosestValueInBstHelper(tree, target, Infinity);
}
​
function findClosestValueInBstHelper(tree, target, closest) {
if (tree === null) return closest;
if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
closest = tree.value;
}
if (target < tree.value) {
return findClosestValueInBstHelper(tree.left, target, closest);
} else if (target > tree.value) {
return findClosestValueInBstHelper(tree.right, target, closest);
} else {
return closest;
}
}
​
exports.findClosestValueInBst = findClosestValueInBst;

TypeScript

class BST {
value: number;
left: BST | null;
right: BST | null;
​
constructor(value: number) {
this.value = value;
this.left = null;
this.right = null;
}
}
​
export function findClosestValueInBst(tree: BST, target: number) {
return findClosestValueInBstHelper(tree, target, tree.value);
}
​
function findClosestValueInBstHelper(tree: BST | null, target: number, closest: number): number {
if (tree === null) return closest;
if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
closest = tree.value;
}
if (target < tree.value) {
return findClosestValueInBstHelper(tree.left, target, closest);
} else if (target > tree.value) {
return findClosestValueInBstHelper(tree.right, target, closest);
} else {
return closest;
}
}

Java

class Program {
public static int findClosestValueInBst(BST tree, int target) {
return findClosestValueInBst(tree, target, Double.MAX_VALUE);
}
​
public static int findClosestValueInBst(BST tree, int target, double closest) {
if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
closest = tree.value;
}
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 {
return (int) closest;
}
}
​
static class BST {
public int value;
public BST left;
public BST right;
​
public BST(int value) {
this.value = value;
}
}
}

C++

#include <cmath>
#include <float.h>
using namespace std;
​
class BST {
public:
int value;
BST *left;
BST *right;
​
BST(int val);
BST &insert(int val);
};
​
int findClosestValueInBst(BST *tree, int target);
int findClosestValueInBstHelper(BST *tree, int target, double closest);
​
int findClosestValueInBst(BST *tree, int target) {
return findClosestValueInBstHelper(tree, target, DBL_MAX);
}
​
int findClosestValueInBstHelper(BST *tree, int target, double closest) {
if (abs(target - closest) > abs(target - tree->value)) {
closest = tree->value;
}
if (target < tree->value && tree->left != NULL) {
return findClosestValueInBstHelper(tree->left, target, closest);
} else if (target > tree->value && tree->right != NULL) {
return findClosestValueInBstHelper(tree->right, target, closest);
} else {
return (int)closest;
}
}

Space-Time Complexity

TimeSpace
AverageO(log(n))O(log(n))
WorseO(n)O(n)

Where n is the number of nodes in the BST

Edit this page