Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int closest = root->val;
        while (root) {
            if (abs(root->val - target) < abs(closest - target)) {
                closest = root->val;
            }
            root = target < root->val ? root->left : root->right;
        }
        return closest;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while (root != null) {
            if (Math.abs(root.val - target) < Math.abs(closest - target)) {
                closest = root.val;
            }
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
var closestValue = function(root, target) {
    let closest = root.val;
    while (root) {
        if (Math.abs(root.val - target) < Math.abs(closest - target)) {
            closest = root.val;
        }
        root = target < root.val ? root.left : root.right;
    }
    return closest;
};
      

Problem Description

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

• Each node in the tree contains a unique integer value.
• You must return the value of the node that is numerically closest to target.
• There will always be exactly one closest value.

For example, given a BST and target = 3.714286, if the tree contains values 1, 2, 3, 4, 5, you should return 4 because it is closest to the target.

Thought Process

The problem asks us to find the value in a binary search tree that is closest to a given target value. The first idea that comes to mind is to check every node in the tree, calculate its distance to the target, and keep track of the closest one we find. This brute-force approach would work, but it does not make use of the special properties of a BST.

In a BST, for any node, all values to the left are smaller, and all values to the right are larger. This property allows us to "steer" our search towards the region where the closest value is more likely to be, rather than visiting every node. This is similar to how binary search works for arrays.

By comparing the current node's value to the target, we can decide whether to move left or right, just as we would in a regular BST search. At each step, we can also update the closest value found so far.

Solution Approach

Let's break down the optimized approach step by step:

1. Initialize: Start with a variable closest set to the root's value. This will keep track of the value we've seen so far that is closest to target.
2. Iterate: While the current node is not null:
   • Compare the current node's value to target. If the distance is less than the distance from closest to target, update closest.
   • If target is less than the current node's value, move to the left child (since smaller values are on the left).
   • Otherwise, move to the right child.
3. Finish: When the traversal is done (i.e., we've reached a null node), return closest.

This approach leverages the BST property to avoid unnecessary checks and ensures that we only visit the path where the closest value could possibly be.

Example Walkthrough

Let's use a sample BST and a target value to see how the algorithm works step by step.

Suppose our BST is:

        4
       / \
      2   5
     / \
    1   3
  

And target = 3.714286.

1. Start at root (4). closest = 4. |4 - 3.714286| = 0.285714.
2. Since target < root.val is false, move right? No, 3.714286 < 4, so move left to 2.
3. At node 2. |2 - 3.714286| = 1.714286. closest remains 4.
4. 3.714286 > 2, so move right to 3.
5. At node 3. |3 - 3.714286| = 0.714286. closest remains 4.
6. 3.714286 > 3, so move right. No right child, so stop.
7. The closest value found is 4.

The algorithm efficiently avoids checking nodes 1 and 5, which are farther from the target.

Time and Space Complexity

• Brute-force approach: Visit every node in the BST and compare to the target. This takes O(N) time and O(1) space (iterative), where N is the number of nodes.
• Optimized approach: By following the BST path, we only visit one node per level. In a balanced BST, this is O(log N) time. In the worst case (unbalanced tree), it could be O(N). Space is O(1) for the iterative solution, as we do not use recursion or extra data structures.

Summary

The key insight for this problem is to use the BST's property to steer our search towards the closest value, rather than checking every node. By always moving left or right depending on the target, we efficiently find the closest value with minimal comparisons. This makes the solution both elegant and efficient, especially for large BSTs.