Closest Binary Search Tree Value
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Binary Search
public int closestValue(TreeNode root, double target) {
if(root == null) throw new RuntimeException("Error");
int res = root.val;
double diff = (double) root.val - target;
while(root != null){
double currDiff = (double) root.val - target;
if(Math.abs(diff) > Math.abs(currDiff))
res = root.val;
diff = currDiff;
if(diff == 0.0) return target;
else if(diff > 0.0)
root = root.left;
else root = root.right;
}
return res;
}
Stack
public int closestValue(TreeNode root, double target) {
Stack <TreeNode> pred = new Stack(), succ = new Stack();
while(root != null){
if(root.val <= target){
pred.push(root);
root = root.right;
}
else{
succ.push(root);
root = root.left;
}
}
return pred.isEmpty() ? succ.peek().val : succ.isEmpty() ? pred.peek().val : (Math.abs(pred.peek().val - target) > Math.abs(succ.peek().val - target)) ? succ.peek().val : pred.peek().val;
}