[Leetcode/Binary Search Tree(BST)] 270. Closest Binary Search Tree Value

BST(Binary Search Tree)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        closest = root.val

        while root:
            # Update closest if this node is nearer,
            # or equally close but smaller than the current closest
            if (abs(root.val - target) < abs(closest - target) or 
    (abs(root.val - target) == abs(closest - target) and root.val < closest)):
                closest = root.val

	# Move left or right based on comparison
            if target < root.val:
                root = root.left
            else:
                root = root.right
        return closest

 

1.  Find the closest value

• abs(root.val - target) < abs(closest - target)
  • This checks if the current node (root.val) is closer to the target than the best one we’ve seen so far (closest).
  • If yes, update closest.

2. Break ties by choosing the smaller value:

• abs(root.val - target) == abs(closest - target) and root.val < closest
  • This checks if both values are equally close to the target.
  • If that’s the case, we prefer the smaller value, as required by the problem.