270. Closest Binary Search Tree Value - Explanation

Description

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

Example 1:

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

Output: 4

Example 2:

Input: root = [1], target = 4.428571

Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

Company Tags

1. Recursive Inorder + Linear search, O(N) time

Python
Java

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        def inorder(r: TreeNode):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        
        return min(inorder(root), key = lambda x: abs(target - x))

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(N)$

Where $N$ is the total number of nodes in the binary tree

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        stack, pred = [], float('-inf')
        
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            
            if pred <= target and target < root.val:
                return min(pred, root.val, key = lambda x: abs(target - x))
                
            pred = root.val
            root = root.right

        return pred

Time & Space Complexity

Time complexity: $O(k)$ in the average case and $O(H+k)$ in the worst case,
Space complexity: $O(H)$

Where $k$ is an index of the closest element and $H$ is the height of the tree.

3. Binary Search, O(H) time

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val

        while root:
            closest = min(root.val, closest, key = lambda x: (abs(target - x), x))
            root = root.left if target < root.val else root.right

        return closest

Time & Space Complexity

Time complexity: $O(H)$
Space complexity: $O(1)$

Where $H$ is the height of the tree.