Closest Binary Search Tree Value

Problem Id: 270 Difficulty: Easy Tag: Binary Search Tag: Tree


Intuition

Just do a binary search. But while we do the binary search, we should visit each node in the path to choose a closest node of the target.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = float('-inf')
        current = root
        while current:
            if abs(target - current.val) < abs(target - closest):
                closest = current.val
            if current.val > target:
                current = current.left
            else:
                current = current.right
        return closest