Leetcode

Closest Binary Search Tree Value

  • Time:O(h)
  • Space:O(h)

C++

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;
  }
};

JAVA

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;
  }
}

Python

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