Leetcode 270 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.

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.

Solution 1: Since it is BST, can be solved in O(logn), keep track the hi and lo boundary, before travel to null. Final result with be the closer of (lo,hi).

 public class Solution {  
   public int closestValue(TreeNode root, double target) {  
     TreeNode x=root;  
     int res=x.val;  
     while (x!=null) {  
       if (target>x.val) x=x.right;  
       else if (target<x.val) x=x.left;  
       else return x.val;  
       if (x!=null && Math.abs(target-x.val)<Math.abs(target-res)) res=x.val;  
     }  
     return res;  
   }  
 }