Practice/Meta/Leetcode 270. Closest Binary Search Tree Value

Leetcode 270. Closest Binary Search Tree Value

CodingMust

Problem

You are given the root of a binary search tree and a target floating-point value. Your task is to find the value in the BST that is numerically closest to the target.

The binary search tree property guarantees that for every node, all values in its left subtree are smaller and all values in its right subtree are larger. Use this property to efficiently navigate the tree.

Requirements

1. Return the integer value of the node that minimizes the absolute difference with the target
2. If multiple nodes are equidistant from the target, return any one of them
3. Utilize the BST property to optimize your search path
4. The tree contains at least one node

Constraints

• The number of nodes in the tree is in the range [1, 10^4]
• 0 ≤= Node.val ≤= 10^9
• -10^9 ≤= target ≤= 10^9
• All node values are unique
• Aim for O(h) time complexity where h is the height of the tree
• O(1) extra space is preferred (excluding recursion stack)

Examples

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286 Output: 4 Explanation: The tree looks like: 4 / \ 2 5 / \ 1 3 The closest value to 3.714286 is 4 (distance ~0.286).

Example 2:

Input: root = [1], target = 4.428571 Output: 1 Explanation: Only one node exists, so it must be the answer.

Example 3:

Input: root = [10,5,15,3,7,null,18], target = 6.5 Output: 7 Explanation: Node 7 is distance 0.5 from target, while node 5 is distance 1.5.