Java iterative and recursive solutions


  • 4
    Y

    Sharing the iterative and recursion solution for this problem. This problem is basically finding the predecessor and successor of a given value in the BST, and returning the one that has the smaller difference. The iterative solution is a bit long, suggestion to shorten it is welcome.

    public int closestValue(TreeNode root, double target) {
            TreeNode greater = null;
            TreeNode smaller = null;
            while(root != null) {
                if(root.val == target) {
                    return root.val;
                } else if(root.val < target) {
                    smaller = root;
                    root = root.right;
                } else {
                    greater = root;
                    root = root.left;
                }
            }
            if(greater == null) {
                return smaller.val;
            }
            if(smaller == null) {
                return greater.val;
            }
            return (greater.val - target) < (target - smaller.val) ? greater.val : smaller.val;
        }
    // iterative
    
    public int closestValue(TreeNode root, double target) {
            TreeNode kid = root.val < target ? root.right : root.left;
            if(kid == null) {
                return root.val;
            }
            int k = closestValue(kid, target);
            return Math.abs(root.val - target) < Math.abs(k - target) ? root.val : k;
        }
    // recursion

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.