Finding the closest number in a Binary Tree to a given target

Question

I have a very simple Binary Tree

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root = TreeNode(8)
root.left = TreeNode(5)
root.right = TreeNode(14)
root.left.left = TreeNode(4)
root.left.right = TreeNode(6)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.right = TreeNode(24)
root.right.right.left = TreeNode(22)

and I implemented a function to find the closest number in the tree to the target (19):

def closest_value(root, target, closest=0):
    if abs(root.val - target) < abs(closest - target):
        closest = root.val
        print(closest)
    if root.left is not None:
        closest_value(root.left, target, closest)
    if root.right is not None:
        closest_value(root.right, target, closest)
    return closest

The result should be obviously 22, but instead i get 8. Surprisungly, when I print all the following 'closest' numbers, the function seems to be working fine: It prints: 8, 14, 22. But why doesn't it return the latest clostest number: 22?

result = closest_value(root, 19)
print('result:', result)

`root.right.right.left` with an assignment looks totally broken to me — roganjosh, Nov 20 '21 at 16:09
@raganjosh what do you mean broken? All the nodes are created in the same way — lukasz21, Nov 20 '21 at 16:11
Because I have _never_ seen anything like that. Properties on properties? How scaleable do you think this will be? — roganjosh, Nov 20 '21 at 16:13
For setting up dummy data, I don't see that there's anything wrong with it. Assigning to attributes of attributes works perfectly fine. The question is about the recursive algorithm, anyway. — CrazyChucky, Nov 20 '21 at 16:16
You need to capture the return value from the recursive calls and return the closest value from the two. — Mark, Nov 20 '21 at 16:17

score 2 · Accepted Answer · edited Nov 20 '21 at 17:10

The value of closest in the first call to closest_value is not updated in the if-statements. Simply assign the value to closest:

def closest_value(root, target, closest=0):
    if abs(root.val - target) < abs(closest - target):
        closest = root.val
    if root.left is not None:
        #assign value
        closest = closest_value(root.left, target, closest)
    if root.right is not None:
        #assign value
        closest = closest_value(root.right, target, closest)
    return closest

result = closest_value(root, 19)
print(result)
# 22

Alain T. · Answer 2 · 2021-11-21T00:54:43.003

You are not using the result of your recursive calls to determine the final returned value.

Perhaps a simpler approach, without pushing down a defaulted parameter would be easier:

def closest(node,value):
    if not node: return float('inf') 
    vals = [node.val, closest(node.left,value), closest(node.right,value)]
    return min(vals,key=lambda v:abs(v-value))

closest(root,19) # 22

One issue, is that this is an O(n) approach that will go through the whole binary tree without leveraging the hierarchy. For a sorted binary tree, you can get a O(logN) solution, by implementing a pair of binary search functions to find the closest node with a value that is <= and the closest node with a value that is >=. Then only apply the absolute value comparison between these two nodes that will have been found in O(logN) time.

def findLE(node,value):
    if not node: return None
    if node.val == value: return node
    if node.val<value:    return findLE(node.right,value) or node
    return findLE(node.right,value)

def findGE(node,value):
    if not node: return None
    if node.val == value: return node
    if node.val>value:    return findGE(node.left,value) or node
    return findGE(node.right,value)

def closestValue(node,value):
    less = findLE(node,value)
    more = findGE(node,value)
    if more and less:
        return min(more.val,less.val,key=lambda v:abs(v-value))
    return (more or less).val

Note that your binary tree is not in sorted order because of the 8 that is left of node 6:

      8
   __/ \_
  5      14
 / \       \
4   6       24
   / \     /
  8   7  22

(you can find the binary tree printing function here)

The second approach requires that it be an actual sorted binary tree, right? It might be worth mentioning that, since the example data in the question is not (entirely) in order. — CrazyChucky, Nov 21 '21 at 00:42
indeed, I didn't realize the binary tree in the example had an element not in the proper order. (adjusted my answer accordingly) — Alain T., Nov 21 '21 at 00:51

Finding the closest number in a Binary Tree to a given target

2 Answers2