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

user_17260221 0
Viewed 188

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)
closest binary-tree python
2 Answers

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
user_40994130

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)

user_52375600
Related