Minimum Absolute Difference in BST

class Solution {
public:
    int smallestDiff = INT_MAX;
    TreeNode* lastVisited = nullptr;
    
    void inOrder(TreeNode* current) {
        if (!current) return;

        inOrder(current->left);

        if (lastVisited != nullptr) {
            smallestDiff = min(smallestDiff, current->val - lastVisited->val);
        }
        lastVisited = current;

        inOrder(current->right);
    }
    
    int findMinDiff(TreeNode* root) {
        inOrder(root);
        return smallestDiff;
    }
};

The solution presented in C++ aims to find the minimum absolute difference between the values of any two nodes in a Binary Search Tree (BST). This approach effectively leverages the properties of BST and in-order traversal to solve the problem with a high degree of efficiency.

** Key elements of the solution include: **

• Definition of two private members in the Solution class:

  • An integer, smallestDiff, initialized to INT_MAX to store the minimum difference.
  • A TreeNode pointer, lastVisited, initialized to nullptr to keep track of the last node visited during the in-order traversal.

• The inOrder function is a recursive method that:

  • Terminates the recursive call if the current node is nullptr.
  • Performs a leftward traversal (visit left subtree).
  • Updates the smallestDiff using the value of the current node and the value of lastVisited if lastVisited is not nullptr.
  • Moves the lastVisited pointer to the current node.
  • Proceeds to rightward traversal (visit right subtree).

• The findMinDiff function:

  • Initiates the in-order traversal from the root.
  • Returns the smallestDiff as the result after completing the traversal.

This solution benefits from the sorted nature of the BST, where an in-order traversal yields values in a non-decreasing order. By checking consecutive elements during this traversal, it efficiently pinpoint the smallest difference without the need for comparing every pair of nodes.

class Solution {
    int smallestDiff = Integer.MAX_VALUE;
    TreeNode previous;

    void traverseInOrder(TreeNode current) {
        if (current == null) {
            return;
        }

        traverseInOrder(current.left);
        if (previous != null) {
            smallestDiff = Math.min(smallestDiff, current.val - previous.val);
        }
        previous = current;
        traverseInOrder(current.right);
    }

    int findMinDiff(TreeNode root) {
        traverseInOrder(root);
        return smallestDiff;
    }
};

The provided Java program solves the problem of finding the minimum absolute difference between the values of any two nodes in a Binary Search Tree (BST). The solution utilizes an in-order traversal to explore the BST and hence leverages the property of BST where in-order traversal leads to values being accessed in ascending order. Below are the core components and steps of the solution:

• A class named Solution is defined with two instance variables:

  • smallestDiff is initialized to Integer.MAX_VALUE to ensure that any smaller difference found during traversal will be updated.
  • previous is a TreeNode object used to keep track of the previously visited node during the in-order traversal.

• The traverseInOrder method is a recursive function:

  • It accepts a TreeNode object representing the current node to be processed.
  • Base case: If the current node is null, the function returns immediately, aiding in navigating leaf nodes.
  • Firstly, the method recursively calls itself on the left child of the current node, ensuring traversal of the tree from the smallest value up.
  • A comparison is conducted (if there’s a previous node) to determine the difference between the current and previous node values. The smallestDiff is updated if the new found difference is smaller.
  • The previous node is then updated to the current node before a recursive call is made to the right child, continuing the in-order traversal.

• The findMinDiff method facilitates the process:

  • Initiates the traversal from the root of the BST.
  • It returns the smallestDiff after the traversal completes, which is the minimum absolute difference found between any nodes in the BST.

Ensure you replace the TreeNode class usage above with an appropriate implementation or definition of the TreeNode as per your existing data structures or frameworks. This code snippet assumes such a class is predefined with at least two member variables: val (value of the node), left and right (pointers to child nodes).

class Solution:
    def findMinDiffInBST(self, node: Optional[TreeNode]) -> int:
        self.smallestGap = float('inf')
        self.lastValue = None

        def traverse_in_order(current):
            if current is None:
                return
            traverse_in_order(current.left)
            if self.lastValue is not None:
                self.smallestGap = min(self.smallestGap, current.val - self.lastValue)
            self.lastValue = current.val
            traverse_in_order(current.right)

        traverse_in_order(node)
        return self.smallestGap

The given solution focuses on finding the minimum absolute difference between any two nodes' values in a Binary Search Tree (BST). The solution employs an in-order traversal, which inherently accesses the BST nodes in an ascending order. Here's a breakdown of the approach:

• A helper function traverse_in_order is defined to perform the in-order traversal of the BST.
• During the traversal, the difference between every two consecutive nodes is computed. self.lastValue holds the value of the previously visited node, ensuring that the difference is calculated between consecutive nodes when traversing.
• The minimum difference self.smallestGap is updated continuously during the traversal whenever a smaller gap is found.

Key aspects of the implementation include:

• Using a class variable self.lastValue to keep track of the last node's value during the in-order traversal.
• Another class variable self.smallestGap is used to store the minimum difference found during traversal. This is initialized to infinity (float('inf')) so that any found difference will be smaller initially.
• Starting the traversal from the root node, the function traverse_in_order is first called.

This method efficiently finds the minimum absolute difference by leveraging the properties of BST and in-order traversal, ensuring a time complexity of O(n) with n being the number of nodes in the BST, since each node is visited exactly once.