Leetcode 0270. Closest Binary Search Tree Value

Problem statement

https://leetcode.com/problems/closest-binary-search-tree-value/

Solution

If target is more that root, check root and right subtree. If target is less or equal than root, check root and left subtree. In my notation dfs(node) will return pair of values: minimum distance between target and elements of subtree with root equal to node.

Complexity

Time and space complexity is $O(h)$, where $h$ is the height of our BST.

Code

class Solution:
    def closestValue(self, root, target):
        def dfs(node):
            if not node: return (float("inf"), -1)
            cand = dfs(node.left) if target < node.val else dfs(node.right)
            return min(cand, (abs(node.val - target), node.val))
            
        return dfs(root)[1]