Skip to content

Instantly share code, notes, and snippets.

@bufordeeds
Created April 3, 2020 03:21
Show Gist options
  • Save bufordeeds/e9ab9dc87b0f84f727a5a2f796bf64cb to your computer and use it in GitHub Desktop.
Save bufordeeds/e9ab9dc87b0f84f727a5a2f796bf64cb to your computer and use it in GitHub Desktop.
Find closest value in BST
/*
Write a function that takes in a Binary Search Tree (BST) and a target integer
value and returns the closest value to that target value contained in the BST.
Each BST node has an integer value , a
left child node, and a right child node. A node is
said to be a valid BST node if and only if it satisfies the BST
property: its value is strictly greater than the values of every
node to its left; its value is less than or equal to the values
of every node to its right; and its children nodes are either valid
BST nodes themselves or None/null.
*/
function findClosestValueInBst(tree, target) {
return findClosestValueInBstHelper(tree, target, Infinity)
}
const findClosestValueInBstHelper = (tree, target, closest) => {
if (tree.value && tree.value === null) {
return closest
}
if (Math.abs(tree.value - target) < Math.abs(closest - target)) {
closest = tree.value
}
if (tree.value > target) {
return findClosestValueInBstHelper(tree.left, target, closest)
}
else if (tree.value < target) {
return findClosestValueInBstHelper(tree.right, target, closest)
}
else {
return closest
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment