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[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
22tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5))
23s = Solution().closestValue(tree, 1.5)
24print(s)