package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**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.*/
public class _270 {

    class GeneralTreeSolution {
        //this finished in 1 ms
        public int closestValue(TreeNode root, double target) {
            if (root == null) {
                return 0;
            }
            double delta = Double.MAX_VALUE;
            return dfs(root, target, delta, root.val);
        }

        private int dfs(TreeNode root, double target, double delta, int closestVal) {
            if (Math.abs(root.val - target) < delta) {
                closestVal = root.val;
                delta = Math.abs(root.val - target);
            }
            int leftVal = closestVal;
            if (root.left != null) {
                leftVal = dfs(root.left, target, delta, closestVal);
            }
            int rightVal = closestVal;
            if (root.right != null) {
                rightVal = dfs(root.right, target, delta, closestVal);
            }
            return (Math.abs(leftVal - target) > Math.abs(rightVal - target)) ? rightVal : leftVal;
        }
    }

    class BSTSolutionRecursive {
        //we can tailor the solution to use the BST feature: left subtrees are always smaller than the root the right subtrees
        //this finished in 0 ms
        public int closestValue(TreeNode root, double target) {
            if (root == null) {
                return 0;
            }
            return dfs(root, target, root.val);
        }

        private int dfs(TreeNode root, double target, int minVal) {
            if (root == null) {
                return minVal;
            }
            if (Math.abs(root.val - target) < Math.abs(minVal - target)) {
                minVal = root.val;
            }
            if (target < root.val) {
                minVal = dfs(root.left, target, minVal);
            } else {
                minVal = dfs(root.right, target, minVal);
            }
            return minVal;
        }
    }

    class GeneralTreeSolutionMoreConcise {
        public int closestValue(TreeNode root, double target) {
            if (root == null) {
                return 0;
            }
            return dfs(root, target, root.val);
        }

        private int dfs(TreeNode root, double target, int minVal) {
            if (root == null) {
                return minVal;
            }
            if (Math.abs(root.val - target) < Math.abs(minVal - target)) {
                minVal = root.val;
            }
            minVal = dfs(root.left, target, minVal);
            minVal = dfs(root.right, target, minVal);
            return minVal;
        }
    }

    class BSTSolutionIterative {
        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;
        }
    }
}

@@ -82,331 +82,100 @@
 e;%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%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.*/%0Apublic class _270 %7B%0A%0A    class GeneralTreeSolution %7B%0A        //
+public class _270 %7B%0A%0A    public static class Solution1 %7B%0A        //A general tree solution, 
 this
@@ -1127,33 +1127,44 @@
  %7D%0A%0A    
+public static 
 class 
-BST
 Solution
 Recursiv
@@ -1159,17 +1159,9 @@
 tion
-Recursive
+2
  %7B%0A 
@@ -1169,16 +1169,41 @@
       //
+ BST solution%0A        // 
 we can t
@@ -2046,46 +2046,73 @@
     
-class GeneralTreeSolutionMoreC
+public static class Solution3 %7B%0A        //a more c
 oncise 
-%7B
+solution
 %0A   
@@ -2731,25 +2731,36 @@
     
+public static 
 class 
-BST
 Solution
 Iter
@@ -2759,9 +2759,27 @@
 tion
-I
+4 %7B%0A        //BST i
 tera
@@ -2783,17 +2783,24 @@
 erative 
-%7B
+solution
 %0A       

refactor 270