Closest Binary Search Tree Value

How it works

The BST property allows us to use binary search. At each node, we compare the target with the current value to decide whether to go left or right. We track the closest value seen so far. If the target is smaller, we go left (there might be a closer smaller value). If the target is larger, we go right (there might be a closer larger value). This approach only visits nodes along a single path from root to leaf.

Steps

1. Initialize the closest value to the root's value.
2. While the current node is not null:
   • If the current value is closer to target than the current closest (or equally close but smaller), update closest.
   • If target < current value, move to the left child.
   • Otherwise, move to the right child.
3. Return the closest value found.

Complexity

• Time complexity: O(H)
• Space complexity: O(1)

Where H is the height of the tree.

Things to watch for

Not Handling Tie-Breaking Correctly

When two values have the same distance to the target, the problem requires returning the smaller value. Using < instead of <= in the comparison can return the wrong answer.

Going the Wrong Direction in BST

Choosing the wrong child based on comparison with target defeats the purpose of binary search. If target is smaller than current value, you must go left (not right) to find potentially closer smaller values.

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val

        while root:
            closest = min(root.val, closest, key = lambda x: (abs(target - x), x))
            root = root.left if target < root.val else root.right

        return closest

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int val, closest = root->val;

        while (root != nullptr) {
            val = root->val;
            closest = abs(val - target) < abs(closest - target)
                || (abs(val - target) == abs(closest - target) && val < closest) ? val : closest;
            root = target < root->val ? root->left : root->right;
        }

        return closest;
    }
};