LeetCode Solutions

270. Closest Binary Search Tree Value

Time: $O(h)$

Space: $O(h)$

			

class Solution {
 public:
  int closestValue(TreeNode* root, double target) {
    // If target < root->val, search left subtree
    if (target < root->val && root->left) {
      const int left = closestValue(root->left, target);
      if (abs(left - target) < abs(root->val - target))
        return left;
    }

    // If target > root->val, search right subtree
    if (target > root->val && root->right) {
      const int right = closestValue(root->right, target);
      if (abs(right - target) < abs(root->val - target))
        return right;
    }

    return root->val;
  }
};
			

class Solution {
  public int closestValue(TreeNode root, double target) {
    // If target < root.val, search left subtree
    if (target < root.val && root.left != null) {
      final int left = closestValue(root.left, target);
      if (Math.abs(left - target) < Math.abs(root.val - target))
        return left;
    }

    // If target > root.val, search right subtree
    if (target > root.val && root.right != null) {
      final int right = closestValue(root.right, target);
      if (Math.abs(right - target) < Math.abs(root.val - target))
        return right;
    }

    return root.val;
  }
}
			

class Solution:
  def closestValue(self, root: Optional[TreeNode], target: float) -> int:
    # If target < root.val, search left subtree
    if target < root.val and root.left:
      left = self.closestValue(root.left, target)
      if abs(left - target) < abs(root.val - target):
        return left

    # If target > root.val, search right subtree
    if target > root.val and root.right:
      right = self.closestValue(root.right, target)
      if abs(right - target) < abs(root.val - target):
        return right

    return root.val