Find Closest Value in BST
At Postman, efficient data retrieval is crucial for features like API discovery, collection management, and environment variable lookups. Imagine a scenario where users are searching for a specific API endpoint or a configuration value, but they might have a slight typo or are looking for a "best match" rather than an exact one. In such cases, finding the closest available item in a structured dataset becomes invaluable.
This problem asks you to implement a core utility function that efficiently finds the numerically closest value to a given target within a Binary Search Tree (BST). This skill is foundational for optimizing search operations in large, ordered datasets, ensuring a responsive and intuitive user experience.
Your task is to implement the findClosestValueInBST function. This function should take the root of a Binary Search Tree (BST) and a target integer as input. It must return the value of the node in the BST whose value is numerically closest to the given target. If the tree is empty, return null.
Specific requirements:
Function Signature:
function findClosestValueInBST(root: TreeNode | null, target: number): number | null
Input:
root: A TreeNode object representing the root of a Binary Search Tree. Each TreeNode has a val (number), left (TreeNode | null), and right (TreeNode | null).target: An integer representing the value to find the closest match for.Output:
number representing the value of the node in the BST that is closest to the target.null if the input root is null (i.e., an empty tree).root is null, return null.target value is present in the BST, that node's value is considered the closest.Examples
Example 1
Input:
root = [4,2,5,1,3], target = 3.5
Output:
3
Note:
The BST has nodes [1, 2, 3, 4, 5]. For target 3.5, both 3 and 4 are equally close (absolute difference 0.5). According to the tie-breaking rule, we return the smaller value, which is 3.
Example 2
Input:
root = [10,5,15,2,7,12,20], target = 13
Output:
12
Note:
The BST has nodes [2, 5, 7, 10, 12, 15, 20]. For target 13, the closest node value is 12 (absolute difference 1). 15 has an absolute difference of 2. So, 12 is returned.
Example 3
Input:
root = [10], target = 8
Output:
10
Note:
The BST contains only one node with value 10. For target 8, the absolute difference is |8 - 10| = 2. Thus, 10 is the closest value.
Example 4
Input:
root = [], target = 5
Output:
null
Note:
The input tree is empty (root is null). As per the requirements, we return null.
Constraints
0 and 10^5.TreeNode.val) will be integers between -10^9 and 10^9.target value will be an integer between -10^9 and 10^9.O(H) where H is the height of the BST, or O(log N) for a balanced BST. In the worst case (skewed tree), this could be O(N).O(H) for a recursive solution (call stack) or O(1) for an iterative solution.target or node values.O(H) or O(log N))?Loading editor...