Minimum Distance Between BST Nodes

class Solution {
public:
    int minimumDifference = INT_MAX;
    TreeNode* previousNode;

    void inorder(TreeNode* node) {
        if (!node) {
            return;
        }

        inorder(node->left);

        if (previousNode) {
            minimumDifference = min(minimumDifference, node->val - previousNode->val);
        }
        previousNode = node;
        
        inorder(node->right);
    }
    
    int getMinimumDifference(TreeNode* root) {
        inorder(root);
        
        return minimumDifference;
    }
};

This C++ solution focuses on finding the minimum distance between values of any two adjacent nodes in a Binary Search Tree (BST) using an inorder traversal approach. The inorder function is crucial for traversing the tree in a way that each node is visited in ascending order, given the properties of BSTs.

The solution utilizes two main members in the Solution class:

• minimumDifference to store the smallest difference found during traversal.
• previousNode to keep track of the node visited immediately before the current one during the inorder traversal.

Here is a breakdown of the solution's process:

1. Initiate an inorder traversal on the BST starting from the root node. As BST properties guarantee that an inorder traversal visits nodes in non-decreasing order, this approach is efficient for comparing the values of adjacent nodes.

2. During each visit to a node, check if there's a previousNode. If it exists:

   • Calculate the difference between the current node's value and the previousNode's value.
   • Update the minimumDifference if this new difference is smaller than the previously recorded differences.

3. Set previousNode to the current node, ensuring that the next node processed can be compared to the correct preceding node.

4. Continue the traversal to the right child of the current node, thus preserving the inorder sequence.

The key outcome of this function is the smallest difference found between the values of two adjacent nodes as determined by the inorder traversal. The performance of the solution hinges on the efficiency of the traversal, which is O(n) where n is the number of nodes in the tree, since each node is visited precisely once. This method is an example of an effective application of classical tree traversal techniques to solve problems concerning properties of node values relative to their position in the tree.

class Solution {
  int minimumDifference = Integer.MAX_VALUE;
  TreeNode lastNode;

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

    inorder(current.left);

    if (lastNode != null) {
      minimumDifference = Math.min(minimumDifference, current.val - lastNode.val);
    }
    lastNode = current;

    inorder(current.right);
  }

  public int minDiffBST(TreeNode treeRoot) {
    inorder(treeRoot);

    return minimumDifference;
  }
};

You will implement a solution to find the minimum distance between any two nodes in a Binary Search Tree (BST) using Java. The given code defines a class Solution that processes the tree using an in-order traversal to efficiently compute the minimum difference between the values of any two nodes.

Solution Overview:

The approach involves traversing the BST in in-order, which ensures nodes are visited in a non-decreasing order. During traversal:

• Store the last visited node.
• Compare the difference between the current and last visited node.
• Update the minimum difference if the current difference is smaller.

Steps to Implement:

1. Declare a class Solution that contains:

   • An integer minimumDifference initialized to Integer.MAX_VALUE.
   • A TreeNode reference lastNode initialized to null.

2. Define a recursive method inorder(TreeNode current) that:

   • Returns immediately if the passed node is null (base case).
   • Recursively processes the left subtree.
   • Updates minimumDifference using the value of the current node and the last visited node if lastNode is not null.
   • Sets the lastNode to the current node.
   • Recursively processes the right subtree.

3. In the method minDiffBST(TreeNode treeRoot), call the inorder method with treeRoot as the argument and return minimumDifference.

Example Usage:

If you have a BST defined and want to find the minimum difference between nodes:

• Create an instance of the Solution class.
• Call the minDiffBST method on the root node of your BST.

This code snippet provides an efficient mechanism to determine the minimum gap between values in a BST, with a time complexity dictated by the tree's traversal, which is O(n).