# Python different recursive solutions.

• ``````# works for normal binary tree
def closestValue1(self, root, target):
if not root:
return 0
self.res = root.val
self.findClosest(root, target)
return self.res

def findClosest(self, root, target):
if root:
if abs(root.val-target) == 0:
self.res = root.val
return  # backtracking
if abs(root.val-target) < abs(self.res - target):
self.res = root.val
self.findClosest(root.left, target)
self.findClosest(root.right, target)

# works for normal binary tree
def closestValue2(self, root, target):
if not root:
return sys.maxint
if not root.left and not root.right:
return root.val
l = self.closestValue(root.left, target)
r = self.closestValue(root.right, target)
return min([root.val, l, r], key=lambda x:abs(x-target))

# works for binary search tree
def closestValue(self, root, target):
if not root:
return sys.maxint
if not root.left and not root.right:
return root.val
node = root.right if target > root.val else root.left
if not node:
return root.val
tmp = self.closestValue(node, target)
return min((tmp, root.val), key=lambda x:abs(x-target))``````

• For

``````    root = TreeNode(2)
root.left = TreeNode(1)
target = sys.maxint
``````

your third solution (the BST one) incorrectly returns sys.maxint.

• Thanks, just added couple more test cases.

• Yes, you are correct, extra checking should be added. It can be fixed by adding: if not node:
return root.val

• Not sure it should be a valid test case, though. This here is Python, but in general the tree values are just 32-bit ints, right? I then find it odd to ask for a 64-bit value.

Btw, while my own solutions still correctly solve the added test case `[2,1], 9223372036854775807.0`, they'd fail `[1,null,2], 9223372036854775807.0` because at that scale the difference to 1 and 2 is lost:

``````>>> 9223372036854775807.0 - 1 == 9223372036854775807.0 - 2
True
``````

My solutions only still work because they encounter the correct answer first, as it's the root value. Allowing such large targets likely breaks everybody's solutions so far. We can all fix it by capping target with "small" values, like doing

``````target = max(min(target, 2**32), -2**32)
``````

before anything else, but that's a bit ugly, especially for recursive solutions, which would cap target again and again unless we write some kind of wrapper.

I think it's unnecessarily "mean" and it would be a good idea if the problem limited target to the possible tree value range (32-bit integer range) because it makes little sense to ask for something far outside.

• Ahaha, I forgot I had thought of a different fix before I went to sleep last night, one that some of my solutions (unintentionally) already use :-) (and caikehe's third does, too). In case of a distance-to-target tie between previous closest value and new value (lower in the tree), simply prefer the new value, not the previous. That way, if the target is very large, the result will still be correct. Works for large negative target as well.

So yeah, that's actually quite neat and doesn't require such an ugly additional fix, so I'm now less against large targets :-)

Edit: Fixed my remaining wrong ones now.

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