Leetcode # 270. Closest Binary Search Tree Value

Problem

https://leetcode.com/problems/closest-binary-search-tree-value/

Solution

Time Complexity: O(log(len(tree)))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def closestValue(self, root: Optional[TreeNode], target: float) -> int:
    closest = root.val
    curr = root
    while curr:
      if curr.val == target: 
        return curr.val
      closest_diff = abs(closest  - target)
      curr_diff    = abs(curr.val - target)
      if curr_diff < closest_diff:
        closest = curr.val
      elif curr_diff == closest_diff:
        closest = min(closest, curr.val)
      curr = curr.right if curr.val < target else curr.left
    return closest

Last Updated on 2024/04/21 by A1go