# 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

"""

 1class 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
8class 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:
16                delta, snode = _delta, node.val
17            recurse(node.left) if (target < node.val) else recurse(node.right)
18        delta, snode = , 
19        recurse(root)
20        return snode
21
22tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5))
23s = Solution().closestValue(tree, 1.5)
24print(s)