4-7 lines recursive/iterative Ruby/C++/Java/Python


  • 96

    Same recursive/iterative solution in different languages.


    Recursive

    Closest is either the root's value (a) or the closest in the appropriate subtree (b).

    Ruby

    def closest_value(root, target)
      a = root.val
      kid = target < a ? root.left : root.right or return a
      b = closest_value(kid, target)
      [b, a].min_by { |x| (x - target).abs }
    end
    

    C++

    int closestValue(TreeNode* root, double target) {
        int a = root->val;
        auto kid = target < a ? root->left : root->right;
        if (!kid) return a;
        int b = closestValue(kid, target);
        return abs(a - target) < abs(b - target) ? a : b;
    }
    

    Java

    public int closestValue(TreeNode root, double target) {
        int a = root.val;
        TreeNode kid = target < a ? root.left : root.right;
        if (kid == null) return a;
        int b = closestValue(kid, target);
        return Math.abs(a - target) < Math.abs(b - target) ? a : b;
    }
    

    Python

    def closestValue(self, root, target):
        a = root.val
        kid = root.left if target < a else root.right
        if not kid: return a
        b = self.closestValue(kid, target)
        return min((b, a), key=lambda x: abs(target - x))
    

    Alternative endings:

        return (b, a)[abs(a - target) < abs(b - target)]
        return a if abs(a - target) < abs(b - target) else b
    

    Iterative

    Walk the path down the tree close to the target, return the closest value on the path. Inspired by yd, I wrote these after reading "while loop".

    Ruby

    def closest_value(root, target)
      path = []
      while root
        path << root.val
        root = target < root.val ? root.left : root.right
      end
      path.reverse.min_by { |x| (x - target).abs }
    end
    

    The .reverse is only for handling targets much larger than 32-bit integer range, where different path values x have the same "distance" (x - target).abs. In such cases, the leaf value is the correct answer. If such large targets aren't asked, then it's unnecessary.

    Or with O(1) space:

    def closest_value(root, target)
      closest = root.val
      while root
        closest = [root.val, closest].min_by { |x| (x - target).abs }
        root = target < root.val ? root.left : root.right
      end
      closest
    end
    

    C++

    int closestValue(TreeNode* root, double target) {
        int closest = root->val;
        while (root) {
            if (abs(closest - target) >= abs(root->val - target))
                closest = root->val;
            root = target < root->val ? root->left : root->right;
        }
        return closest;
    }
    

    Python

    def closestValue(self, root, target):
        path = []
        while root:
            path += root.val,
            root = root.left if target < root.val else root.right
        return min(path[::-1], key=lambda x: abs(target - x))
    

    The [::-1] is only for handling targets much larger than 32-bit integer range, where different path values x have the same "distance" (x - target).abs. In such cases, the leaf value is the correct answer. If such large targets aren't asked, then it's unnecessary.

    Or with O(1) space:

    def closestValue(self, root, target):
        closest = root.val
        while root:
            closest = min((root.val, closest), key=lambda x: abs(target - x))
            root = root.left if target < root.val else root.right
        return closest

  • 1

    Thank you Stefan!


  • 0

    Great codes! Besides the lambda function in the Python code, I read again nice codes like return (a, b)[abs(b - target) < abs(a - target)] that uses a bool variable to index two values. Well, have seen this before, also from your codes :-)

    BTW, at first I do not use the properties of BST and so the following code is a little more verbose. But then I realize it may be able to solve a follow-up problem: Closest Binary Tree Value? Is that right :-)

    class Solution {
    public:
        int closestValue(TreeNode* root, double target) {
            if (!root) return INT_MAX;
            if (!(root -> left) && !(root -> right)) return root -> val;
            int left = closestValue(root -> left, target);
            int right = closestValue(root -> right, target);
            double td = abs(root -> val - target), ld = abs(left - target), rd = abs(right - target);
            if (td < ld) return td < rd ? root -> val : right;
            else return ld < rd ? left : right;
        } 
    };

  • 0

    @jianchao.li.fighter I think your code will fail if target is closer to INT_MAX than to any value in the tree. Bad idea trying to encode "none" as a value that is also a valid value.


  • 0

    Hi, Stefan. Thanks for your suggestions. Well, I have updated my code. Now it will call closestValue on a subtree only if it exists. The code is as follows.

    class Solution {
    public:
        int closestValue(TreeNode* root, double target) {
            bool left = !!(root -> left), right = !!(root -> right);
            int kid, val = root -> val;
            if (left && right) {
                int l = closestValue(root -> left, target);
                int r = closestValue(root -> right, target);
                kid = (abs(l - target) < abs(r - target) ? l : r);
            }
            else if (left) kid = closestValue(root -> left, target);
            else if (right) kid = closestValue(root -> right, target);
            else return val;
            return abs(val - target) < abs(kid - target) ? val : kid;
        }
    }; 
    

    Then I submit it to OJ to check for its correctness at least in the case of BST. But I got a wrong answer in the case [2,1], 9223372036854775807.0. The expected output is 2 but the code gives 1. I debug the code in MSVC 2012 and both val and kid get the correct value (2 and 1 respectively). But then the comparison abs(val - target) < abs(kid - target) fails. I try to check for the two abstract values by printing them out

    printf("%f\n", abs(2 - target));
    printf("%f\n", abs(1 - target));
    

    And the output is quite strange (they are the same):

    9223372036854775800.000000
    9223372036854775800.000000
    

    Well, Stefan, could you please help me figure out the reason? Thanks!


  • 0

    The reason is that those are doubles, which have about 53 bits precision, but that target needs 63 bits. So neither 2 - target nor 1 - target are represented exactly, they're both rounded to the same nearest possible double value. I have btw fixed all my solutions so they can handle such very large targets, and even infinity.


  • 0

    It's odd, though, that you get 9223372036854775800. On the OJ, your test gives me 9223372036854775808 (last digit differs) and I did a little Python-test on my PC which says the closest two values are 9223372036854775808 (1 larger than 9223372036854775807) and 9223372036854774784 (1023 smaller than 9223372036854775807).


  • 0

    Hi, Stefan. Thanks for your detailed reply. Well, the results of my test are obtained in Microsoft Visual Studio 2012. Is the difference due to different compilers?

    If double's cannot be handled correctly, could we still come up with a correct solution if the BST is replaced by a simple binary tree?

    BTW, I wonder how you got those two closest values in Python? Thanks!


  • 0

    Maybe just the printing is odd. What do you get with printf("%.20f\n", ...)?

    To fix it, you could overwrite val with kid if kid's distance to target is smaller or if it's equal and kid lies between val and target (i.e., val < kid <= target or val > kid >= target).

    Nearest possible doubles:

    >>> target = 9223372036854775807
    >>> prev = None
    >>> for t in range(target - 3000, target + 3000):
            f = float(t)
            if f > prev:
                print '%f' % f, int(f), f >= target
                prev = f
    
    9223372036854772736.000000 9223372036854772736 False
    9223372036854773760.000000 9223372036854773760 False
    9223372036854774784.000000 9223372036854774784 False
    9223372036854775808.000000 9223372036854775808 True
    9223372036854777856.000000 9223372036854777856 True
    

  • 1

    Nearest possible doubles, done in C++ (showing 9223372036854775807.0 as well as the next smaller three and next larger three):

    int closestValue(TreeNode* root, double target) {
        double d = 9223372036854775807.0;
        long *p = (long*) &d;
        *p -= 3;
        for (int i=0; i<7; ++i) {
            printf("%.20f\n", d);
            ++(*p);
        }
        return 0;
    }
    

    That prints:

    9223372036854772736.00000000000000000000
    9223372036854773760.00000000000000000000
    9223372036854774784.00000000000000000000
    9223372036854775808.00000000000000000000
    9223372036854777856.00000000000000000000
    9223372036854779904.00000000000000000000
    9223372036854781952.00000000000000000000

  • 0

    Hi, Stefan. Thanks for your work, especially the nice scripts for printing nearest doubles! Well, I try printf("%.20f\n", ...); as you suggest, and the results just have got more zeros after the decimal point.

    9223372036854775800.00000000000000000000
    9223372036854775800.00000000000000000000
    

    BTW, I update the code as you suggest: now I will also return kid if its distance to target is equal to that of val and it lies between val and target. The code is as follows and it works :-)

    class Solution {
    public:
        int closestValue(TreeNode* root, double target) {
            bool left = !!(root -> left), right = !!(root -> right);
            int kid, val = root -> val;
            if (left && right) {
                int l = closestValue(root -> left, target);
                int r = closestValue(root -> right, target);
                kid = (abs(l - target) < abs(r - target) ? l : r);
            }
            else if (left) kid = closestValue(root -> left, target);
            else if (right) kid = closestValue(root -> right, target);
            else return val;
            return (abs(kid - target) < abs(val - target) || (abs(kid - target) == abs(val - target) && between(target, val, kid)))? kid : val;
        }
    private:
        bool between(double target, int val, int kid) {
            if (kid > val) return kid <= target;
            if (kid < val) return kid >= target;
            return false;
        } 
    };
    

    In fact, I am still wondering whether it is safe to write abs(kid - target) == abs(val - target) or should I replace it with something like abs(abs(kid - target) - abs(val - target)) < epsilon?


  • 0

    Found someone saying printf's precision is to blame.

    I think you also need to use between to find out which of the left and right kid is better.

    wondering whether it is safe to write abs(kid - target) == abs(val - target)

    When kid and val are on the same side of target, I think it's safe because subtracting the same value (target) should be monotonous and abs either leaves both alone or turns both into a subtraction from the same value (target) which again should be monotonous. But I'm uncertain about when they're on different sides of target. Hmm. In any case, I think working with an epsilon there is more likely to cause an error than to fix one.

    Your between is buggy, btw, check the second line.


  • 0

    Try printf("%.30g\n", ...), someone said g might be better.


  • 0
    This post is deleted!

  • 0

    Hi, Stefan. Thank you for your efforts!

    • I think you also need to use between to find out which of the left and right kid is better.

    Thanks. Do you think the following code will work?

    class Solution {
    public: 
        int closestValue(TreeNode* root, double target) {
            bool left = !!(root -> left), right = !!(root -> right);
            int kid, val = root -> val;
            if (left && right) {
                int l = closestValue(root -> left, target);
                int r = closestValue(root -> right, target);
                /* Use between to check which one is better */
                if (abs(l - target) < abs(r - target)) kid = l;
                else if (abs(l - target) > abs(r - target)) kid = r;
                else kid = (between(target, l, r) ? r : l);
            }
            else if (left) kid = closestValue(root -> left, target);
            else if (right) kid = closestValue(root -> right, target);
            else return val;
            return (abs(kid - target) < abs(val - target) || (abs(kid - target) == abs(val - target) && between(target, val, kid)))? kid : val;
        }
    private:
        bool between(double target, int val, int kid) {
            if (kid > val) return kid <= target;
            if (kid < val) return kid >= target;
            return false;
        }
    };
    
    • Your between is buggy, btw, check the second line.

    Oh, an obvious mistake. Well, I have updated it now. Wow, even such a buggy code gets accepted by the OJ, creating sufficient test cases is really hard.

    Well, I try it in Microsoft Visual Studio 2012 and the result is still the same:

    9223372036854775800
    9223372036854775800
    

  • 0

    Do you think the following code will work?

    I must admit that it's now so long and complicated that I didn't study it thoroughly :-P. But it looks alright.

    I just still don't know whether there could be kid < target < val and kid is closer to target but abs(kid - target) is larger than abs(val - target). And if that can happen, I don't know how to handle it.

    Edit: Hmm... actually, since kid and val are both 32-bit integers, then if target is between them, it is also in 32-bit int range and then that hypothetical problem case can't happen because in that range, doubles represent integers and integers + 0.5 exactly.


  • 0

    Hi, Stefan. Thanks for your nice comments. Well, double's seem to cause troubles :-)


  • 0
    T

    in c++, maybe should use fabs rather than abs


  • 0

    Does it have some advantage?


  • 0
    A
    This post is deleted!

Log in to reply
 

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