# 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.
Example:

• traverse the tree, using BST constraints to get to the closest value.
• keep track of the deltas, between target and each visited node.
• return the id of the closest delta seen

Time: Worst O(n), Best O(1), Average O(log n)
Space: Worst O(n), Best O(1), Average O(log n)

Input: root = [4,2,5,1,3], target = 3.714286
4
/ \
2 5
/ \
1 3

Output: 4

"""

 1 class TreeNode:
2     def __init__(self, val=0, left=None, right=None):
3         self.val = val
4         self.left = left
5         self.right = right
6
7
8 class Solution:
9
10     def closestValue(self, root, target):
11         def recurse(node):
12             if not node:
13                 return
14             _delta = abs(target - node.val)
15             if _delta < delta[0]:
16                 delta[0], snode[0] = _delta, node.val
17             recurse(node.left) if (target < node.val) else recurse(node.right)
18         delta, snode = [1000], [0]
19         recurse(root)
20         return snode[0]
21
22 tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5))
23 s = Solution().closestValue(tree, 1.5)
24 print(s)