How to Find Closest Value in a BST?
Difficulty: Easy
The Problem
Prerequisite, before continuing with this article you should be familiar with constructing a binary search tree. Read through my series on constructing a BST starting here.
We are given a binary search tree and a target value. We are asked to find an existing value on the BST that is closest to the target value. Let’s use the BST provided below and set our target value to 16.
The answer is 15 because the next closest value is 18 and 18 is farther away from 16 than 15. This logic will be the corner stone of our final algorithm.
Solution
Since we know that BST traversal is pretty much the same for all BST traversing algorithms we can borrow some logic from our find method that I presented a few weeks ago, it can be found here. That logic dictates that so long as the node we are positioned on is not empty then lets move to either the left or right child node of our current node based on some logic. In our case, we will move to the left child node if the target value is less than the value of our node we are currently positioned on and vice versa. At the same time, we will keep track of our reoccuring closest value by doing a little bit of math. I promise it is very straight forward. Let’s start building the algorithm.
In the above code, we are setting our starting points and starting to traverse the BST. We set closestVal to the value of the first node we always first encounter on a BST which is the root node, currentNode tracks our current. positioning on the tree which currently is the root node. Since we have to traverse, we will implement iteration and tell the algorithm to continue traversing the tree so long as currentNode is truthy or not null. Lets look at the next step.
In the above code, we are determining which distance, between the closestVal & currentNode.value, from the target value is shorter. We are looking for the shortest distance because that represents a measurement that is closer to the target value. After doing the math, we will reassign closestVal to the value of currentNode if currentNode's value is closer to target’s value. If it is not then closestVal retains it’s current value. Take note that we want to take the absolute difference because we don’t want any negative numbers. However, we are not finished because we haven’t finished traversing the BST. We continue traversing our BST by moving our currentNode's position. Let’s take a look at how to do this.
The above code shows how to traverse the BST by comparing the target value to the value of currentNode. If the target is greater, then with the aid of the properties of a BST, which dictate that the entire left subtree of a node must be less than any node on the right subtree of the same node, then we will move our currentNode to the right child node of the current node and vice versa. If we happen to encounter a node that is equal to the target well then we found our answer and we can terminate the loop with a break statement. Finally, we return our resulting closestVal to terminate the function once after we have traversed the tree until we reached an empty node or if we found a node that holds a value that matches the target value.
Time Space Complexity
In the case of an average case, our time complexity would be O(log(n)) logarithmic time because we are narrowing our search for the node that is closest to the target value. We aren’t traversing the entire BST in our average case for time complexity. However, in our worst case, we would be traversing the entire BST which would be O(n) linear time. Why? Well lets take the following BST.
The above image represent a tree that satisfies BST validations but it doesn’t lend itself to the advantages of BST properties because there is no way to narrow our search. Say our target value is 30 then we know our answer would be 28 however we would have to traverse the entire BST to reach 28 therefore it is linear time because we are traversing the BST based on the number of nodes that exist.
In the case of space complexity, since we are using iteration and not recursion thus avoiding stack call usage, we will always be running in constant time O(1).
Conclusion
As we can see, the logic for finding the closest value in a BST is not complex at all. I recommend first getting comfortable with knowing how to traverse a BST and the most natural way of doing that is building a BST. You can learn how to do so by following my series on constructing a BST which is now complete. I hope this was helpful and your feedback is welcomed. Stay safe and happy coding!
