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

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ public class Solution {     private double min = Double.MAX_VALUE;     private int ans = 0;     public int closestValue(TreeNode root, double target) {         if (root == null) {             return Integer.MAX_VALUE;         }                   closestValueHelper(root, target);                   return ans;     }           private void closestValueHelper(TreeNode root, double target) {         if (root == null) {             return;         }                   if (Math.abs((double) root.val - target) < min) {             min = Math.abs((double) root.val - target);             ans = root.val;         }                   if (root.val > target) {             closestValueHelper(root.left, target);         } else if (root.val < target) {             closestValueHelper(root.right, target);         }     } }

Iterative solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ public class Solution {     public int closestValue(TreeNode root, double target) {         if (root == null) {             throw new NullPointerException("Tree must be non-empty");         }                   int result = 0;         double gap = Double.MAX_VALUE;                   while (root != null) {             if (root.val == target) {                 return root.val;             }                           double dist = Math.abs(root.val - target);             if (dist < gap) {                 result = root.val;                 gap = dist;             }                           if (target > root.val) {                 root = root.right;             } else if (target < root.val) {                 root = root.left;             }         }         return result;     } }