Skip to content

270. Closest Binary Search Tree Value 👍

  • Time: $O(h)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int closestValue(TreeNode* root, double target) {
    // If target < root->val, search the 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 the 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int closestValue(TreeNode root, double target) {
    // If target < root.val, search the 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 the 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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def closestValue(self, root: Optional[TreeNode], target: float) -> int:
    # If target < root.val, search the 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 the 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