# Closest Binary Search Tree Value Leetcode Solution

Difficulty Level Easy
HBO Walmart Global techViews 942

## Problem Statement :

Closest Binary Search Tree Value Leetcode Solution – Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

## Example :

### Example 1 ```Input: root = [4,2,5,1,3], target = 3.714286
Output: 4```

### Example 2

```Input: root = , target = 4.428571
Output: 1```

## Constraints : ## Explanation :

• Given the root of a binary search tree and a target value.
• We need to return a node value of BST that is closest to the target.
• From Example 1, target = 3.714286, and the nodes with values 3 and 4 are the possible nodes that are closer to the target.
• But the closest node is 4 with the target.

For node 3,  closestness=|3.714286 – 3| = 0.714286

For node 4,  closestness=|3.714286 – 4| = 0.285714

## Observation :

• In the BST all the left child nodes have a value smaller than the parent value, and also, all the right child nodes have a value greater than the parent value.
• If we do an In-order traversal, we can see that the nodes in the BST are sorted in increasing order.

## Approach :

• From the above observation, we can iteratively use the Binary Search algorithm.
• We will travel the BST from the root and while traversing we will calculate the closeness of every node with the target.
• If the root value is equal to the target then root.val.

if(root.val==target) return  root.val;

• If the root value is smaller than the target then we will go to the right child of the root.

if(root.val<target) root=root.right;

• If the root value is greater than the target then we will go to the left child of the root.

if(root.val>target) root=root.left;

## Code for Closest Binary Search Tree Value :

### Java  Code  for Closest Binary Search Tree Value

```class Solution {
public int closestValue(TreeNode root, double target) {
double closestValue=Integer.MAX_VALUE;
int closestNode=root.val;
while(root!=null){
if(closestValue>Math.abs(target-root.val)){
closestValue=Math.abs(target-root.val);
closestNode=root.val;
}
if(root.val==target)return root.val;
if(root.val<target){
root=root.right;
}
else if(target<root.val){
root=root.left;
}
}
return closestNode;
}
}```

### C++ Code  for Closest Binary Search Tree Value

```class Solution {
public:
int closestValue(TreeNode* root, double target) {
double closestValue=INT_MAX;
int closestNode=root->val;
while(root!=NULL){
if(closestValue>abs(target-root->val)){
closestValue=abs(target-root->val);
closestNode=root->val;
}
if(root->val==target)return root->val;
if(root->val<target){
root=root->right;
}
else if(target<root->val){
root=root->left;
}
}
return closestNode;
}
};```

## Complexity Analysis for Closest Binary Search Tree Value Leetcode Solution:

### Time Complexity

O(H), since we are going down from root to the leaf.

### Space Complexity

O(1), constant space.

Translate »