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;
    }

results matching ""

    No results matching ""