Closest Binary Search Tree Value

To find the value in a binary search tree (BST) that is closest to a given target, you can perform an in-order traversal while keeping track of the closest value found so far. Since the tree is a BST, the in-order traversal will process the nodes in ascending order, allowing you to compare each value to the target.

Here’s a step-by-step approach:

  1. Initialize Variables: Initialize variables to track the closest value and the minimum difference found so far.
  2. In-Order Traversal: Perform an in-order traversal of the tree.
  3. Compare Values: During the traversal, compare each node’s value to the target and update the closest value if a smaller difference is found.
  4. Handle Ties: If there are multiple answers with the same difference, return the smallest value.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        def in_order_traversal(node):
            nonlocal closest_val
            if not node:
                return

            in_order_traversal(node.left)

            # Compare the current node's value to the target
            if abs(node.val - target) < abs(closest_val - target):
                closest_val = node.val
            elif abs(node.val - target) == abs(closest_val - target):
                closest_val = min(closest_val, node.val)

            in_order_traversal(node.right)

        closest_val = float('inf')
        in_order_traversal(root)
        return closest_val

Key Takeaways

  • The problem can be solved by performing an in-order traversal and comparing each value to the target.
  • The time complexity of this solution is (O(N)), where (N) is the number of nodes in the tree. The space complexity is also (O(N)) in the worst case, as it may need to store the entire tree in the call stack. In a balanced BST, the space complexity would be (O(\log N)).

LC official solution works. Here is the code for solving the problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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

Bard failed. Read the editorial on LC.