DSA problem
Closest Binary Search Tree Value
Given the root of a binary search tree and a target value target (a floating-point number), return the value in the BST that is closest to target. If two values are equally close, return the smaller one.
A brute-force scan of every node and a running minimum-distance check would take O(n) time and ignore the BST structure entirely. Since the tree is ordered, however, you can do much better: each comparison of target against node.val tells you exactly which side of the tree could contain an even closer value.
Specifically, if target < node.val, every value in the right subtree is greater than node.val and therefore farther from target than node.val itself; the only possibly-closer values live in the left subtree. The symmetric argument holds for target > node.val. This means a single root-to-leaf walk suffices.
The optimal solution walks one pointer down the tree, keeping track of the closest value seen so far. Update the candidate whenever |node.val - target| is strictly smaller, with ties broken toward the smaller value to honor the tie-breaking rule. The traversal stops at a null child, giving O(h) time and O(1) space.
Examples
root = [4,2,5,1,3], target = 3.7142864root = [1], target = 4.4285711root = [2,1,3], target = 2.02Constraints
- The number of nodes in the tree is in the range [1, 10^4].
- 0 <= Node.val <= 10^9
- -10^9 <= target <= 10^9
- When two values are equally close, return the smaller one.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.