Closest Binary Search Tree Value Leetcode Solution

Table of Contents

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 = [1], 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;
    }
};