Minimum Absolute Difference in BST

🏠 ⬅️ ➡️

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3] Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49] Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 104].
  • 0 <= Node.val <= 105

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 2
    real(DP), dimension(n) :: x, y
    real(DP) :: z
    type(TreeNode), pointer :: root

    x = [4._DP, 2._DP]
    y = [6._DP, 1._DP]
    call solve(x, y, z)
    write (unit=error_unit, fmt='(ES24.16)') z

    x = [1._DP, 0._DP]
    y = [48._DP, 12._DP, 49._DP]
    call solve(x, y, z)
    write (unit=error_unit, fmt='(ES24.16)') z

contains

    subroutine solve(x, y, z)
        implicit none
        real(DP), dimension(:), intent(in) :: x, y
        real(DP), intent(out) :: z
        type(TreeNode), pointer :: root

        allocate(root)
        call build_tree(root, x, y)
        z = min_abs_diff(root)

        deallocate(root)
    end subroutine solve

    recursive function min_abs_diff(node) result(res)
        implicit none
        class(TreeNode), pointer, intent(in) :: node
        real(DP) :: res

        if (.not. associated(node)) then
            res = huge(res)
        elseif (.not. associated(node%left) .and. .not. associated(node%right)) then
            res = 0._DP
        else
            res = min(min_abs_diff(node%left), min_abs_diff(node%right))
        end if

        if (associated(node%left) .and. associated(node%right)) then
            res = min(res, abs(node%val - node%right%val))
            res = min(res, abs(node%val - node%left%val))
        end if
    end function min_abs_diff

    subroutine build_tree(root, x, y)
        implicit none
        type(TreeNode), pointer, intent(inout) :: root
        real(DP), dimension(:), intent(in) :: x, y
        integer :: i, j

        do i = 1, size(x)
            allocate(root%left)
            root%left%val = x(i)
            do j = 1, size(y)
                if (y(j) == x(i)) then
                    root%left%left => null()
                    root%left%right => null()
                    exit
                end if
            end do
            call build_tree(root%left, x, y)

            allocate(root%right)
            root%right%val = x(i)
            do j = 1, size(y)
                if (y(j) == x(i)) then
                    root%right%left => null()
                    root%right%right => null()
                    exit
                end if
            end do
            call build_tree(root%right, x, y)
        end do
    end subroutine build_tree

end program main

type :: TreeNode
    real(DP) :: val
    type(TreeNode), pointer :: left
    type(TreeNode), pointer :: right
end type TreeNode
❌ Compiled
❌ Executed
❌ Correct
🌐 Data from online sources 
class TreeNode:
    def __init__(self, x: int):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        result = float('inf')
        prev = None

        def inorderTraversal(node):
            nonlocal result, prev
            if node is None:
                return
            inorderTraversal(node.left)
            if prev is not None:
                result = min(result, node.val - prev.val)
            prev = node
            inorderTraversal(node.right)

        inorderTraversal(root)
        return result

The algorithm uses an in-order traversal of the binary search tree to find the minimum absolute difference between the values of any two different nodes in the tree. Since it's an in-order traversal, we are going through the nodes in ascending order, which makes it easier to calculate and compare differences. During the traversal, we maintain a prev variable that stores the previously visited node to calculate the difference with the current node. If the difference between the current node and the previous node is smaller than the current result, we update the result accordingly. At the end of the traversal, the result will be the minimum absolute difference between any two different nodes in the tree.

🌐 Data from online sources 
#include <algorithm>
#include <climits>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int result = INT_MAX, prev = -1;
        minimumDifference(root, result, prev);
        return result;
    }

    void minimumDifference(TreeNode* node, int& result, int& prev) {
        if (!node) return;
        minimumDifference(node->left, result, prev);
        if (prev != -1) {
            result = std::min(result, node->val - prev);
        }
        prev = node->val;
        minimumDifference(node->right, result, prev);
    }
};

The algorithm uses an in-order traversal of the binary search tree to find the minimum absolute difference between the values of any two different nodes in the tree. Since it's an in-order traversal, we are going through the nodes in ascending order, which makes it easier to calculate and compare differences. During the traversal, we maintain a prev variable that stores the previously visited node to calculate the difference with the current node. If the difference between the current node and the previous node is smaller than the current result, we update the result accordingly. At the end of the traversal, the result will be the minimum absolute difference between any two different nodes in the tree.