Closest Binary Search Tree Value

Intuition

Because the tree is a BST, the target's comparison with a node tells us which side could hold something even closer. Track the closest value seen so far, initialized to the root's value, and refine it as we descend. At each node, compute its distance to the target and adopt it as the new best when it is strictly nearer, or when it ties the current best but has a smaller value (honoring the tie-break rule). Then, if the target is less than the current node's value the only chance to improve lies to the left, otherwise to the right. Moving one step at a time toward the target keeps the search on the height of the tree rather than the whole tree.

Algorithm walkthrough

1. 1Initialize closest to the root's value as a starting candidate.
2. 2While the current node is non-null, measure |node.val - target| and compare it to |closest - target|.
3. 3Update closest to node.val when the new distance is strictly smaller, or equal but node.val is smaller (tie-break).
4. 4If target is less than node.val, move to the left child; otherwise move to the right child.
5. 5Repeat until the walk runs off the tree (current node becomes null).
6. 6Return closest, the nearest value encountered along the path.

Implementation

class Solution:
    def closestValue(self, root: 'TreeNode', target: float) -> int:
        closest = root.val
        while root is not None:
            diff = abs(root.val - target)
            best = abs(closest - target)
            if diff < best or (diff == best and root.val < closest):
                closest = root.val
            if target < root.val:
                root = root.left
            else:
                root = root.right
        return closest