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

• 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``````

• Thank you Stefan!

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

• @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.

• 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
``````

• 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.

• 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).

• 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!

• 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
``````

• 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``````

• 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`?

• 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.

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

• This post is deleted!

• 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
``````

• 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.

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

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

• Does it have some advantage?

• This post is deleted!

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