240. Closest Binary Search Tree Value
You are given the root of a non-empty binary search tree whose nodes hold integers, plus a floating-point number target.
Return the node value whose distance to target is smallest. If two values sit at exactly the same distance, return the smaller of them.
Visiting every node works, but the BST ordering lets you home in on the answer along a single root-to-leaf path — aim for time proportional to the tree's height.
Example 1:
Input: root = [4, 2, 5, 1, 3], target = 3.714286
Output: 4
Explanation: Distances to 3.714286: value 4 is 0.285714 away, value 3 is 0.714286 away, everything else is farther. 4 wins.
Example 2:
Input: root = [1], target = 4.428571
Output: 1
Explanation: A single-node tree has only one candidate, so the answer is 1 no matter the target.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -10⁶ ≤ Node.val ≤ 10⁶
- Node values are distinct and satisfy the BST property.
- -10⁷ ≤ target ≤ 10⁷ (target is a floating-point number)
- On a distance tie, the answer is the smaller value.
Hints:
Any traversal that touches every node and keeps a running best (comparing distances, breaking ties toward the smaller value) is already correct — it just ignores the BST structure.
In a BST, comparing target with the current node tells you which subtree could hold anything closer: go left if target < node.val, right otherwise.
Both the value just below the target and the value just above it lie on that single descent path — so tracking a best along the path is enough.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [4, 2, 5, 1, 3], target = 3.714286
Expected output: 4