Problem

Write a function to find the closest value in the BST to a given target integer.

The BST contains BST nodes. Each node stores an integer in a property called “value”, and two children in properties called “left” and “right”.

A Node is said to be a BST node if and only if it satisfies the following property:

• Its value is greater than the nodes values to its left,
• Its value is less than or equal to the node values to its right
• Both its children are either BST nodes or None values.

We’ll define the BST and the function that finds the closest value to the target integer contained in the BST.

Sample Input:

    10      Target: 12
    /  \
    5    15
   / \   |  \
  2  5  13   22
 /        \
1          14

Output: 13

import math


class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left is None:
                self.left = BST(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BST(value)
            else:
                self.right.insert(value)
        return self


def findClosestValueInBst(tree, target):
    """
    First start with infinity as the closest value to the target,
    so that we have something to compare to the
    absolute value difference of (first node - target)
    """
    closest = math.inf
    root = tree
    while root is not None:
        if root.value == target:
            return root.value

        if abs(root.value - target) < abs(closest - target):
            closest = root.value

        if root.value < target:
            root = root.right
        elif root.value > target:
            root = root.left
        else:
            break
    return closest

bst = BST(10).insert(5).insert(2).insert(5).insert(1).insert(5).insert(15) \
    .insert(13).insert(14).insert(22)

findClosestValueInBst(bst, 12)

13