💬 Discord
Sign In
NeetCode #398LC-270EasyTreesNC Algo100
← Back to All Problems

#398 · #270 · Closest Binary Search Tree Value(最接近的二叉搜索树值)

📌 Problem Statement & Constraints

Given the root of a binary search tree and a floating-point target, return the value in the tree closest to the target. If several values are equally close, return the smallest. Constraints: the number of nodes is in [1, 10^4], 0 <= Node.val <= 10^9, 0 <= target <= 10^9.

💡 Core Algorithmic Approaches

  1. Descend the BST guided by target, keeping the closest value seen so far.
  2. At each node, update the best if the current value is closer, or equally close but smaller.
  3. Then move left when target < node.val and right otherwise.
  4. This is O(h) instead of the O(n) full traversal, because the BST ordering bounds where the closest value can be.

💻 Benchmark Python3 Implementation

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        best = root.val
        cur = root
        while cur:
            d_cur = abs(cur.val - target)
            d_best = abs(best - target)
            # strictly closer, or equally close but smaller
            if d_cur < d_best or (d_cur == d_best and cur.val < best):
                best = cur.val
            if target < cur.val:
                cur = cur.left             # values only get smaller
            else:
                cur = cur.right
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(h): one root-to-leaf descent.
💾 Space Complexity
O(1) for the iterative version.

⚠️ Interview Pitfalls & Follow-ups

  • Traversing the whole tree: O(n) and unnecessary -- the BST ordering prunes the search.
  • Comparing with <= instead of the explicit tie-break: <= would keep the larger value on a tie, contradicting the requirement.
  • Assuming the answer is unique: the statement allows ties, so the smallest must be selected.
  • Stopping the descent after finding a close value: the closest value may be deeper along the path.