# LeetCode 270: Closest Binary Search Tree Value

## Problem Restatement

We are given the root of a binary search tree and a target value.

The target can be a floating-point number.

We need to return the value in the BST that is closest to the target.

If multiple values are equally close, return the smaller value. The tree contains between `1` and `10^4` nodes, node values are in `[0, 10^9]`, and the target is in `[-10^9, 10^9]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a BST and a numeric target |
| Output | Integer node value closest to `target` |
| Tree rule | Left values are smaller, right values are larger |
| Tie rule | Return the smaller value |

Example function shape:

```python
def closestValue(root: Optional[TreeNode], target: float) -> int:
    ...
```

## Examples

Example 1:

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

Tree:

```text
    4
   / \
  2   5
 / \
1   3
```

Compare distances:

| Value | Distance from target |
|---|---:|
| `3` | `0.714286` |
| `4` | `0.285714` |
| `5` | `1.285714` |

The closest value is:

```python
4
```

Answer:

```python
4
```

Example 2:

```python
root = [1]
target = 4.428571
```

There is only one node.

Answer:

```python
1
```

## First Thought: Visit Every Node

A direct solution is to traverse the whole tree.

For every node:

1. Compute the absolute difference from `target`.
2. Keep the value with the smallest difference.
3. Return the best value after visiting all nodes.

This works for any binary tree.

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

        def dfs(node: Optional[TreeNode]) -> None:
            nonlocal closest

            if node is None:
                return

            if abs(node.val - target) < abs(closest - target):
                closest = node.val
            elif abs(node.val - target) == abs(closest - target):
                closest = min(closest, node.val)

            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return closest
```

This is correct, but it does not use the BST ordering.

## Problem With Full Traversal

A full DFS visits every node.

So the time complexity is:

```python
O(n)
```

The BST property gives us a better direction.

If the target is smaller than the current node value, closer values may exist on the left.

If the target is larger than the current node value, closer values may exist on the right.

So we can walk down one path instead of traversing the whole tree.

## Key Insight

At every node, the current node is a candidate answer.

After checking it:

- If `target < node.val`, move left.
- If `target > node.val`, move right.
- If `target == node.val`, return immediately.

This works because a BST is ordered.

For example, at node `4`:

```python
target = 3.714286
```

Since the target is smaller than `4`, the only subtree that might contain a closer value is the left subtree.

The right subtree contains values larger than `4`, so those values are even farther from a target below `4`.

## Algorithm

1. Set `closest = root.val`.
2. Start at `node = root`.
3. While `node` exists:
   - If `node.val` is closer to `target`, update `closest`.
   - If the distance ties, keep the smaller value.
   - If `target < node.val`, move to `node.left`.
   - Otherwise, move to `node.right`.
4. Return `closest`.

## Walkthrough

Use:

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

Start:

```python
closest = 4
node = 4
```

Distance:

```python
abs(4 - 3.714286) = 0.285714
```

Move left because:

```python
3.714286 < 4
```

Now:

```python
node = 2
```

Distance:

```python
abs(2 - 3.714286) = 1.714286
```

`2` is farther than `4`, so keep `closest = 4`.

Move right because:

```python
3.714286 > 2
```

Now:

```python
node = 3
```

Distance:

```python
abs(3 - 3.714286) = 0.714286
```

`3` is farther than `4`, so keep `closest = 4`.

Move right because:

```python
3.714286 > 3
```

There is no right child.

Return:

```python
4
```

## Correctness

The algorithm keeps `closest` as the best value seen so far on the search path.

At every visited node, it compares that node against the current best answer. Therefore `closest` is always the closest value among all visited nodes.

The BST property lets the algorithm choose one direction. If `target` is smaller than `node.val`, all values in the right subtree are greater than `node.val`, so they cannot be closer than `node.val` itself. Since `node.val` has already been considered, skipping the right subtree is safe. The symmetric argument applies when `target` is larger than `node.val`.

Thus every skipped subtree cannot contain a better answer than a value already considered on the path.

When traversal ends, `closest` is the closest value in the BST.

The tie rule is handled by choosing the smaller value when distances are equal.

## Complexity

Let `h` be the height of the tree.

| Metric | Value | Why |
|---|---|---|
| Time | `O(h)` | We walk down one root-to-leaf path |
| Space | `O(1)` | Iterative traversal uses only a few variables |

For a balanced BST, `h = O(log n)`.

For a skewed BST, `h = O(n)`.

## Implementation

```python
from typing import Optional

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

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

        while node is not None:
            current_diff = abs(node.val - target)
            closest_diff = abs(closest - target)

            if current_diff < closest_diff:
                closest = node.val
            elif current_diff == closest_diff and node.val < closest:
                closest = node.val

            if target < node.val:
                node = node.left
            elif target > node.val:
                node = node.right
            else:
                return node.val

        return closest
```

## Code Explanation

Initialize the answer with the root value:

```python
closest = root.val
```

The tree has at least one node, so this is safe.

At every node, compare the current value with the best value so far:

```python
current_diff = abs(node.val - target)
closest_diff = abs(closest - target)
```

If the current node is closer, update:

```python
closest = node.val
```

For a tie, use the smaller value:

```python
elif current_diff == closest_diff and node.val < closest:
    closest = node.val
```

Then move in the only useful BST direction:

```python
if target < node.val:
    node = node.left
elif target > node.val:
    node = node.right
else:
    return node.val
```

If we find the exact target, no value can be closer, so we return immediately.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(5),
    )
    assert s.closestValue(root, 3.714286) == 4
    assert s.closestValue(root, 3.2) == 3
    assert s.closestValue(root, 4.0) == 4

    root = TreeNode(1)
    assert s.closestValue(root, 4.428571) == 1

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.closestValue(root, 2.5) == 2

    root = TreeNode(10, TreeNode(5), TreeNode(15))
    assert s.closestValue(root, -100.0) == 5
    assert s.closestValue(root, 100.0) == 15

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `3.714286` | Official-style example |
| `3.2` | Target closer to lower value |
| Exact target | Immediate best possible answer |
| Single node | Smallest tree |
| Tie case | Returns smaller value |
| Target below all values | Returns minimum |
| Target above all values | Returns maximum |