Getting to the topic of binary search trees (bst) in my studies was exciting and intimidating at first, but after repeated practice and working with a friend, I have begun to get a grasp on binary search trees. In this problem, we'll be working through a binary search tree to find the closest element to a given target. Here is a quick definition of a binary search tree.
Problem
We are given a binary search tree and a target, and we are tasked with finding a value in the binary search tree that is closest to value of the given target. In this problem, there will only be one closest value.
Approach
First off, we'll be using an iterative approach to solving this problem. We will need to keep track of the current node we are looking at in the bst, as well as which node's value is closest to our target.
We'll implement a while loop to go through the bst as long as the current node's value is NOT null.
A conditional is going to help us assign a node that is closest in value to the given target, as well as reassign when we find another node even closer in value to the target.
We'll use two conditionals to determine if we move to the current node's left child node or the right child node, dependent upon the target's value relative to the current node.
Our final answer will be the node value closest to the target value.
Solution
We set up our main function that takes in two arguments, a binary search tree and target value.
function findClosestValueInBst(tree, target) {
}
A helper function is going to be useful here, so the focus will be on it for now, returning to the main function at the end. An important thing to note is that we added a third parameter, closest, which will be the node with the value closest to the target value. We also assign a variable currentNode equal to tree to keep track of where we are in the bst.
We will build out the helper function outside of the main function, but then return it in our main function. When the helper fn is in the main function, note that the third argument is tree.value, because we will use that as our initial closest value to the target value.
function findClosestValueInBst(tree, target) {
return helperToFindClosestValue(tree, target, tree.value)
}
function helperToFindClosestValue(tree, target, closest) {
let currentNode = tree;
}
Implement a while loop so we continue going through our tree as long as a node is there, so while it is NOT equal to null.
function helperToFindClosestValue(tree, target, closest) {
let currentNode = tree;
while (currentNode !== null) {
//work will go here
}
}
Next step is very important because we are reassigning what the closest value is to the target. We do this by comparing the absolute value of the difference between the target and the closest value against the absolute value of the difference between the target and current node value we are looking at.
If the absolute value of the difference between the target and current node value is smaller than the absolute value of the difference between the target and the closest value, then we reassign closest to the current node value. Hopefully the code is clearer than that explanation.
function helperToFindClosestValue(tree, target, closest) {
let currentNode = tree;
while (currentNode !== null) {
if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
closest = currentNode.value;
}
}
}
That takes care of keeping track of the closest value.
Next, we work on two conditionals to help us navigate the bst, going either left or right down the tree.
If our target is greater than the current node's value, then we navigate down the right child node's side because anything on the left will be less than the current node's value, meaning the absolute value difference will be farther from our target value.
If our target is less than the current node's value, then we navigate down the left child node's side because anything on the right will be greater than the current node's value, meaning the absolute value difference will be farther from our target value.
function helperToFindClosestValue(tree, target, closest) {
let currentNode = tree;
while (currentNode !== null) {
if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
closest = currentNode.value;
}
if (target > currentNode.value) {
currentNode = currentNode.right;
} else if (target < currentNode.value) {
currentNode = currentNode.left
}
}
}
Almost there, next we consider the case where the target is actually equal to the value of the current node. If that's the case, we break out of the loop and return the closest value.
function helperToFindClosestValue(tree, target, closest) {
let currentNode = tree;
while (currentNode !== null) {
if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
closest = currentNode.value;
}
if (target > currentNode.value) {
currentNode = currentNode.right;
} else if (target < currentNode.value) {
currentNode = currentNode.left
} else {
break;
}
}
return closest;
}
All together, it looks like this:
function findClosestValueInBst(tree, target) {
return helperToFindClosestValue(tree, target, tree.value)
}
function helperToFindClosestValue(tree, target, closest) {
let currentNode = tree;
while (currentNode !== null) {
if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
closest = currentNode.value;
}
if (target > currentNode.value) {
currentNode = currentNode.right;
} else if (target < currentNode.value) {
currentNode = currentNode.left
} else {
break;
}
}
return closest;
}
Resources
Oldest comments (0)