Closest Binary Search Tree Value Link
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
- Given target value is a floating point.
- You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:
Input: root = [4,2,5,1,3], target = 3.714286
5
/ \
2 6
/ \
1 4
Output: 4
Solution:
A binary search solution can be achieved to solvw this efficiently with using the concepts of binary trees as well.
In this, we will traverse like this: Go to the left if target is smaller than current root value, and Go to the right otherwise. Choose the closest to target value at each step. This will reduce our complexity as much as possible.
Implementation:
Java:
class Solution {
public int closestValue(TreeNode root, double target) {
long minVal = Long.MAX_VALUE;
while (root != null) {
if (Math.abs(root.val - target) < Math.abs(minVal - target)) {
minVal = root.val;
}
if (target < root.val) {
root = root.left;
} else {
root = root.right;
}
}
return minVal == Long.MAX_VALUE ? 0 : (int) minVal;
}
}
Complexity Analysis:
- Time complexity: O(H) since here one goes from root down to a leaf.
- Space complexity: O(1).
