Closest Binary Search Tree Value - Leetcode Solution

Problem Statement:

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Example:

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

Solution:

The solution to this problem is to traverse the BST to search for the node which is closest to the target. Since the BST is sorted, we can compare the value of the current node with the target and move either to the left or right subtree based on the comparison.

We will use the following steps to solve the problem:

1. Initialize a variable ‘res’ to track the node value closest to the target.
2. Traverse the BST in a top-down order using the following condition:
   • If the target is less than the value of the current node, move left.
   • If the target is greater than the value of the current node, move right.
   • If the target is equal to the value of the current node, return the node.
   • Update the 'res' variable with the node value upon visiting it.
3. Return the ‘res’ variable after traversal.

Below is the Python implementation of the above approach:

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        
        res = root.val
        
        while root:
            if abs(root.val - target) < abs(res - target):
                res = root.val
                
            if target < root.val:
                root = root.left
            elif target > root.val:
                root = root.right
            else:
                return root.val
            
        return res

Time Complexity:

As we have to traverse the whole tree to find the closest node, the worst-case time complexity of this solution is O(n), where n is the number of nodes in the tree.

Space Complexity:

The space complexity of this solution is O(1) since we are not using any extra space for computation.

1