Closest Binary Search Tree Value

🏠 ⬅️ ➡️

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, 104].
  • 0 <= Node.val <= 109
  • -109 <= target <= 109
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, iostat_end, DP => REAL64
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    type :: node_type
        real(kind=DP) :: val
        class(node_type), pointer :: left => null(), right => null()
    end type node_type
    type (node_type), pointer :: root
    real(kind=DP) :: target
    character(len=*), parameter :: fmt = '(A,F10.5)'
    integer :: ios

    call get_root(root)
    read (unit=unit_in, fmt='(F10.5)', iostat=ios) target
    if (ios /= 0 .and. ios /= iostat_end) then
        write (unit=error_unit, fmt='("error reading input: ", A)') trim(adjustl(str(ios)))
        stop 1
    end if
    if (ios == iostat_end) then
        ! No more input, exit
        stop 0
    end if

    call solve(root, target)

contains

    subroutine get_root(root)
        type (node_type), pointer :: root
        real(kind=DP) :: val
        integer :: ios

        do
            read (unit=unit_in, fmt='(F10.5)', iostat=ios) val
            if (ios /= 0 .and. ios /= iostat_end) then
                write (unit=error_unit, fmt='("error reading input: ", A)') trim(adjustl(str(ios)))
                stop 1
            end if
            if (ios == iostat_end) then
                ! No more input, exit
                exit
            end if
            allocate (root)
            root%val = val
            call get_left(root%left)
            call get_right(root%right)
        end do
    end subroutine get_root

    subroutine get_left(left)
        type (node_type), pointer :: left
        real(kind=DP) :: val
        integer :: ios

        do
            read (unit=unit_in, fmt='(F10.5)', iostat=ios) val
            if (ios /= 0 .and. ios /= iostat_end) then
                write (unit=error_unit, fmt='("error reading input: ", A)') trim(adjustl(str(ios)))
                stop 1
            end if
            if (ios == iostat_end) then
                ! No more input, exit
                exit
            end if
            allocate (left)
            left%val = val
            call get_left(left%left)
            call get_right(left%right)
        end do
    end subroutine get_left

    subroutine get_right(right)
        type (node_type), pointer :: right
        real(kind=DP) :: val
        integer :: ios

        do
            read (unit=unit_in, fmt='(F10.5)', iostat=ios) val
            if (ios /= 0 .and. ios /= iostat_end) then
                write (unit=error_unit, fmt='("error reading input: ", A)') trim(adjustl(str(ios)))
                stop 1
            end if
            if (ios == iostat_end) then
                ! No more input, exit
                exit
            end if
            allocate (right)
            right%val = val
            call get_left(right%left)
            call get_right(right%right)
        end do
    end subroutine get_right

    subroutine solve(root, target)
        type (node_type), pointer :: root
        real(kind=DP), intent(in) :: target
        real(kind=DP) :: diff, min_diff
        type (node_type), pointer :: current

        current => root
        min_diff = huge(min_diff)
        do while (associated(current))
            diff = abs(current%val - target)
            if (diff < min_
❌ Compiled
❌ Executed
❌ Correct 
module BinarySearchTree

    implicit none

    type :: Node
        integer :: val
        type(Node), pointer :: left
        type(Node), pointer :: right
    end type Node

    interface
        function closestValue(root, target) result(closest)
            type(Node), pointer, intent(in) :: root
            real(kind=8), intent(in) :: target
            integer :: closest
        end function closestValue
    end interface

contains

    function closestValue(root, target) result(closest)
        type(Node), pointer, intent(in) :: root
        real(kind=8), intent(in) :: target
        integer :: closest
        real(kind=8) :: diff

        if (associated(root)) then
            closest = root%val
            diff = abs(real(root%val, kind=8) - target)

            if (target < real(root%val, kind=8)) then
                closest = closestValue(root%left, target)
                if (abs(real(closest, kind=8) - target) < diff) then
                    diff = abs(real(closest, kind=8) - target)
                end if
            else
                closest = closestValue(root%right, target)
                if (abs(real(closest, kind=8) - target) < diff) then
                    diff = abs(real(closest, kind=8) - target)
                end if
            end if
        end if
    end function closestValue

end module BinarySearchTree

program main
    use BinarySearchTree
    implicit none
    type(Node), pointer :: root
    integer :: target
    integer :: closest

    ! Example 1
    root => Node(val=4, left => Node(val=2), right => Node(val=5))
    target = 3.714286
    closest = closestValue(root, target)
    write (*,*) closest

    ! Example 2
    root => Node(val=1)
    target = 4.428571
    closest = closestValue(root, target)
    write (*,*) closest

end program main
🌐 Data from online sources 
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        closest = root.val
        while root:
            if abs(target - closest) > abs(target - root.val):
                closest = root.val
            root = root.left if target < root.val else root.right
        return closest

The algorithm uses a while loop to traverse the binary search tree. During the iteration, we continuously update the closest variable with the current node's value if the current node's value is closer to the target than the previous closest value. The algorithm follows the binary search tree's property, taking the left branch if the target is less than the current node's value and the right branch if the target is greater than the current node's value. On reaching a null node, the algorithm terminates and returns the closest value found.

🌐 Data from online sources 
class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int closest = root->val;
        while (root != nullptr) {
            if (abs(target - closest) > abs(target - root->val)) {
                closest = root->val;
            }
            root = target < root->val ? root->left : root->right;
        }
        return closest;
    }
};

The algorithm uses a while loop to traverse the binary search tree. During the iteration, we continuously update the closest variable with the current node's value if the current node's value is closer to the target than the previous closest value. The algorithm follows the binary search tree's property, taking the left branch if the target is less than the current node's value and the right branch if the target is greater than the current node's value. On reaching a null node, the algorithm terminates and returns the closest value found.