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:

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)