@@ -0,0 +1,2073 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0Aimport com.freetymekiyan.algorithms.utils.Utils.TreeNode;%0A%0A/**%0A * Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.%0A * %3Cp%3E%0A * Note:%0A * Given target value is a floating point.%0A * You are guaranteed to have only one unique value in the BST that is closest to the target.%0A * %3Cp%3E%0A * Company Tags: Microsoft, Google, Snapchat%0A * Tags: Tree, Binary Search%0A * Similar Problems: (M) Count Complete Tree Nodes, (H) Closest Binary Search Tree Value II%0A */%0Apublic class ClosestBinarySearchTreeValue %7B%0A%0A    /**%0A     * Binary Search. Recursive%0A     * Get root's value first, a.%0A     * If target %3C root's value, the next root will be left child.%0A     * Else it should be right child.%0A     * If the next root is null:%0A     * %7C Just return root's value.%0A     * Else get the closest value of next root, b.%0A     * Compare a and b, return the closer one.%0A     */%0A    public int closestValue(TreeNode root, double target) %7B%0A        int a = root.val;%0A        TreeNode child = target %3C a ? root.left : root.right;%0A        if (child == null) %7B%0A            return a;%0A        %7D%0A        int b = closestValue(child, target);%0A        return Math.abs(a - target) %3C Math.abs(b - target) ? a : b;%0A    %7D%0A%0A    /**%0A     * Binary Search. Iterative.%0A     * Initialize answer as root's value.%0A     * While root is not null:%0A     * %7C If target is closer to current node's value then result:%0A     * %7C   Update result to current node's value.%0A     * %7C Otherwise, result remains the same.%0A     * %7C If target %3C current's value, move current node to left child.%0A     * %7C Else move current node to right child.%0A     * Return result.%0A     */%0A    public int closestValue2(TreeNode root, double target) %7B%0A        TreeNode cur = root;%0A        int res = root.val;%0A        while (cur != null) %7B%0A            if (Math.abs(target - cur.val) %3C Math.abs(target - res)) %7B%0A                res = cur.val;%0A            %7D%0A            cur = target %3C cur.val ? cur.left : cur.right;%0A        %7D%0A        return res;%0A    %7D%0A%0A%7D%0A

add closest binary search tree value