• 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
``````