270 Closest Binary Search Tree Value

Problem Statement

link: LeetCode.cn LeetCode

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

Example:

Input: root = [4,2,5,1,3], target = 3.714286 Output: 4

Input: root = [1], target = 4.428571 Output: 1

Solution Approach

In this problem, we aim to find the value in a binary search tree (BST) that is closest to a given target. The solution approach involves traversing the BST while keeping track of the closest value to the target.

Algorithm

1. Initialization: Start with the root node and initialize variables to track the closest value and its absolute difference from the target.
2. Traverse and Update: Traverse the BST while updating the closest value based on the absolute difference at each step.
3. Return Result: After the traversal, return the identified closest value to the target, considering any multiple answers and prioritizing the smallest value.

Implement

    class Solution:
  def closestValue(self, root: Optional[TreeNode], target: float) -> int:
      node = root
      result = [None, float("inf")]
      while node:
          diff = abs(node.val - target)
          if diff < result[1]:
              result = [node.val, diff]
          if diff == result[1] and node.val < result[0]:
              result = [node.val, diff]
          if target == node.val:
              return node.val
          elif target < node.val:
              node = node.left
          else:
              node = node.right
      return result[0]
       

    
    

Twitter  facebook  Email