# 270 Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

* Given target value is a floating point.
* You are guaranteed to have only one unique value in the BST that is closest to the target.

**The Idea:** Perform a regular binary search, except rather than searching for the element explicitly, continually update the closest difference with the target value.

**Complexity:** O(logN) time and O(|height|) space

```python
class Solution:
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """

        min_diff = [sys.maxsize]
        min_val = [root.val]

        def search(root):
            if not root:
                return
            cur_min_diff = abs(root.val - target)
            if cur_min_diff < min_diff[0]:
                min_diff[0] = cur_min_diff
                min_val[0] = root.val

            if target < root.val:
                return search(root.left)
            else:
                return search(root.right)

        search(root)
        return min_val[0]
```

**Python Solution**

Same idea, but now iterative.

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

import sys


class Solution:
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """

        dist = sys.maxsize
        closest_val = sys.maxsize

        while root:
            cur_dist = abs(root.val - target)
            if cur_dist < dist:
                closest_val = root.val 
                dist = cur_dist
            if target > root.val:
                root = root.right
            else:
                root = root.left

        return closest_val
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/270-closest-binary-search-tree-value.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.