Frontend School

Find Closest Value in BST

DSA
easy

Find Closest Value in BST

Easy
Tree
Binary Search Tree
Search

Overview

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.

What you need to do / Task

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:

  1. Efficiency: Your solution should leverage the properties of a BST to perform the search efficiently.
  2. Tie-breaking: If there are two nodes whose values are equally close to the target, you must return the value of the node that is numerically smaller.

Input & output

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:

  • A 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).

Clarifications

  • Empty Tree: If root is null, return null.
  • Target Exists: If the target value is present in the BST, that node's value is considered the closest.
  • Node Values: All node values in the BST will be unique integers.
  • BST Properties: You can assume the input tree is a valid Binary Search Tree.

Examples

1

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.

2

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.

3

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.

4

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

Constraints & assumptions

  • The number of nodes in the BST will be between 0 and 10^5.
  • Node values (TreeNode.val) will be integers between -10^9 and 10^9.
  • The target value will be an integer between -10^9 and 10^9.
  • The BST is guaranteed to have unique integer values for its nodes.
  • Time complexity for an L3 candidate is expected to be 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).
  • Space complexity is expected to be O(H) for a recursive solution (call stack) or O(1) for an iterative solution.

Out of scope

  • You do not need to validate if the input tree is indeed a valid BST.
  • You do not need to handle non-integer target or node values.

What interviewers evaluate

  • Correctness: Does the solution correctly identify the closest value, including tie-breaking rules and edge cases?
  • Efficiency: Does the solution leverage BST properties for optimal time complexity (O(H) or O(log N))?
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand?
  • Edge Cases: Are empty trees, single-node trees, and cases where the target itself is in the tree handled properly?

Loading editor...