Closest Binary Search Tree Value

Problem Statement

In this problem, you are given the root of a Binary Search Tree (BST) and a numerical target value. Your task is to find the value within the BST that is closest to the specified target. A BST is characterized by each node having nodes values greater than all the node values in its left subtree and less than or equal to all the node values in its right subtree. Amongst values that are equally close to the target, you are required to return the smallest such value. This requires processing and searching through the tree efficiently to find the value that best satisfies this condition.

Examples

Example 1

Input:

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

Output:

4

Example 2

Input:

root = [1], target = 4.428571

Output:

1

Constraints

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 109
• -109 <= target <= 109

Approach and Intuition

In order to solve this problem most effectively, we can leverage the properties of the BST combined with a methodological approach to find the closest value. Here's how:

1. Initialize a variable, say closest, to a very large number initially (Conceptually, this could be akin to infinity).
2. Traverse through the binary tree. There are two primary decisions during the traversal:
   • If the current node value is greater than the target, move to the left child of the node.
   • If the current node value is less than the target, move to the right child of the node.
   • This utilizes the sorted property of BST to cut down half of the tree in our search.
3. Keep track of the difference between the target and the current node's value:
   • Calculate the absolute difference between the target and the current node value.
   • If this difference is less than the difference calculated for closest, update closest to the current node value.
   • If the difference is the same but the current node offers a smaller value than the current closest, then update the closest.
4. Continue this till all nodes that could potentially house a closer value are exhausted (i.e., when the node is null).

By employing this approach, one ensures an efficient run time that leverages the BST properties, requiring travel across only some branches of the tree rather than examining each node. This approach ensures a run-time complexity driven by the height of the tree, which can often be much better than examining every node in the tree. This targeted traversal method is encapsulated by the difference comparisons and potential updating of the closest variable, effectively narrowing down the closest value by elimination.

Solutions

class Solution {
  public int nearestValue(TreeNode node, double target) {
    int currentValue, nearest = node.val;
    while (node != null) {
      currentValue = node.val;
      nearest = Math.abs(currentValue - target) < Math.abs(nearest - target)
          || (Math.abs(currentValue - target) == Math.abs(nearest - target) && currentValue < nearest) ? currentValue : nearest;
      node = target < node.val ? node.left : node.right;
    }
    return nearest;
  }
}