Problem Explanation

The problem is asking to find the minimum difference among two different nodes in a Binary Search Tree. To find that, we can use the in-order traversal. A Binary Search Tree (BST) has the property that all nodes on the left subtree are less than the node and all nodes on the right are greater. Therefore, performing an in-order traversal (i.e., left-root-right), which sorts the BST in ascending order, can allow us to easily access adjacent values.

We only compare the current node with its immediate predecessor in the in-order sequence, making the problem more manageable.

Approach

This solution walks through the Binary Search Tree (BST) in an in-order traversal approach. By walking in-order, we are guaranteed to go from the smallest to the largest node because of the property of BST. We keep track of the previous node we passed, calculate the difference with the current node, and keep the minimum of all the differences.

Let's walk through an example.

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

This tree can be represented as:

1
2    
3          4
4        /   \
5      2      6
6     / \
7    1   3

The nodes in in-order traversal are: 1,2,3,4,6. And the differences are: abs(1-2), abs(2-3), abs(3-4), and abs(4-6). The minimum of these differences is 1. This result will be returned as output.

C++ Solution

1
2C++
3class Solution {
4 public:
5  int minDiffInBST(TreeNode* root) {
6    int ans = INT_MAX; //Initialize answer variable with maximum integer
7    inorder(root, ans); //start with root node, pass answer reference to function
8    return ans; //return answer value
9  }
10
11 private:
12  int pred = -1; //Predecessor of current node
13
14  void inorder(TreeNode* root, int& ans) {
15    if (root == nullptr) // if node is null, return
16      return;
17
18    inorder(root->left, ans); //recursive call to left node
19    if (pred >= 0) //if predecessor is not null, calculate minimum difference
20      ans = min(ans, root->val - pred); 
21    pred = root->val; //update predecessor to current node
22    inorder(root->right, ans); //recursive call to right node
23  }
24};

Python Solution

1
2Python
3class Solution:
4 def minDiffInBST(self, root):
5    self.res = float('inf')   # Initialize result with maximum value
6    self.pre = None  # Initialize predecessor with None
7    self.inOrder(root) #start process from root
8    return self.res  #return result
9    
10 def inOrder(self, root):
11    if root:   #if root node is not None,
12        self.inOrder(root.left) #recursive call to left node
13        if self.pre: #if predecessor is not None, calcualte minimum difference
14            self.res = min(self.res, root.val - self.pre.val)
15        self.pre = root #update predecssor with current node
16        self.inOrder(root.right) #recursive call to right node

Note

Java, JavaScript, and C# solutions are not required. But you can easily implement the above Python or C++ solution in your preferred programming language by following the same logic. Just make sure to use equivalent syntax and data structures of that language.# Java Solution

Similar to the Python and C++ solutions, we can implement the in-order traversal in Java as well.

1
2java
3class Solution {
4    private TreeNode previousNode = null;  // Initialize predecessor with null
5    private int minimumDifference = Integer.MAX_VALUE; // Initialize result with maximum value
6
7    public int minDiffInBST(TreeNode root) {
8        if (root == null)   // if root node is null, return 0
9            return 0;
10        inOrder(root); // else start process from root
11        return minimumDifference; // return result
12    }
13    public void inOrder(TreeNode root) {
14        if (root == null) // if current node is null, return
15            return;
16        inOrder(root.left); // recursive call to left node
17        if (previousNode != null) // if predecessor is not null, calculate minimum difference
18            minimumDifference = Math.min(minimumDifference, root.val - previousNode.val);
19        previousNode = root; // update predecessor with current node
20        inOrder(root.right); // recursive call to right node
21    }
22}

JavaScript Solution

1
2javascript
3var minDiffInBST = function(root) {
4    var min = Number.MAX_SAFE_INTEGER; // Initialize result with maximum integer
5    var pre = -1; // Initialize predecessor with -1
6    var inOrder = function(root){ // start with root node
7       if(root === null) // if node is null, return
8           return;
9       inOrder(root.left); // recursive call to left node
10       if(pre >= 0) // if predecessor is not null, calculate minimum difference
11           min = Math.min(min, root.val - pre);
12       pre = root.val; // update predecessor with current node
13       inOrder(root.right); //recursive call to right node
14    }
15    inOrder(root); //begin traversal from root
16    return min; // return result
17};

In all cases, we compare the current node with its immediate predecessor in the in-order sequence to compute the minimum difference. This approach significantly reduces the workload by eliminating the need to compare every pair of nodes. Implementing this solution requires an understanding of Binary Search Tree properties and in-order traversal.