Closest Binary Search Tree Value Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Bloomberg Facebook Goldman Sachs Google Microsoft Snapchat
HBO Walmart Global techViews 175

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

Closest Binary Search Tree Value Leetcode Solution

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

Example 2

Input: root = [1], target = 4.428571
Output: 1

Constraints :

Closest Binary Search Tree Value Leetcode Solution

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 »