Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        prev = None
        min_diff = float('inf')
        
        def inorder(node):
            nonlocal prev, min_diff
            if not node:
                return
            inorder(node.left)
            if prev is not None:
                min_diff = min(min_diff, node.val - prev)
            prev = node.val
            inorder(node.right)
        
        inorder(root)
        return min_diff
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int minDiff = INT_MAX;
        int prev = -1;
        inorder(root, prev, minDiff);
        return minDiff;
    }
    
    void inorder(TreeNode* node, int& prev, int& minDiff) {
        if (!node) return;
        inorder(node->left, prev, minDiff);
        if (prev != -1)
            minDiff = std::min(minDiff, node->val - prev);
        prev = node->val;
        inorder(node->right, prev, minDiff);
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

class Solution {
    Integer prev = null;
    int minDiff = Integer.MAX_VALUE;
    
    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return minDiff;
    }
    
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;
        inorder(node.right);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDiffInBST = function(root) {
    let prev = null;
    let minDiff = Infinity;
    
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        if (prev !== null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;
        inorder(node.right);
    }
    
    inorder(root);
    return minDiff;
};
      

Problem Description

You are given the root of a Binary Search Tree (BST). Your task is to find the minimum difference between the values of any two different nodes in the tree.

Key constraints:

• Each node in the BST contains a unique integer value.
• You must return the smallest possible absolute difference between values of any two nodes.
• Each input will have at least two nodes.

Thought Process

At first glance, you might consider comparing every possible pair of nodes and calculating their absolute difference, keeping track of the minimum. However, since the number of pairs grows quickly as the tree gets larger, this approach is inefficient.

Then, you remember that a Binary Search Tree has a special property: for any node, all values in the left subtree are less, and all values in the right subtree are greater. If you perform an in-order traversal (left, root, right), you will visit the nodes in ascending order. This means the smallest difference will always be found between two consecutive nodes in this order.

By shifting your thinking from "compare every pair" to "just compare neighbors in sorted order," you can dramatically improve efficiency.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Use In-Order Traversal:
   • In-order traversal of a BST visits nodes in ascending order.
   • We only need to compare each node with the previous node visited.
2. Track Previous Value:
   • Keep a variable (let's call it prev) to remember the value of the last node visited.
   • Initialize prev as null or an invalid value before traversal starts.
3. Track Minimum Difference:
   • Keep a variable (e.g., min_diff) to store the smallest difference found so far, initialized to a very large number.
4. Update on Each Visit:
   • During traversal, when you visit a node, if prev is not null, compute the difference between the current node's value and prev.
   • Update min_diff if this difference is smaller than the current min_diff.
   • Set prev to the current node's value before moving to the next node.
5. Return the Result:
   • After the traversal, min_diff will hold the minimum absolute difference between any two nodes in the BST.

This approach leverages the sorted order property of in-order traversal in BSTs and ensures we only need a single pass through the tree.

Example Walkthrough

Let's use the following BST as an example:

      4
     / \
    2   6
   / \
  1   3
  

Steps:

1. Start in-order traversal at the leftmost node (1). prev is null, so no comparison.
2. Move to node 2. Difference: 2 - 1 = 1. min_diff becomes 1. prev is now 2.
3. Move to node 3. Difference: 3 - 2 = 1. min_diff remains 1. prev is now 3.
4. Move to node 4. Difference: 4 - 3 = 1. min_diff remains 1. prev is now 4.
5. Move to node 6. Difference: 6 - 4 = 2. min_diff remains 1.

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(N^2) because you would need to compare every pair of nodes (where N is the number of nodes).
  • Space Complexity: O(N) if you store all node values for comparison.
• Optimized Approach (In-Order Traversal):
  • Time Complexity: O(N) since each node is visited once.
  • Space Complexity: O(H) where H is the height of the tree (for the recursion stack). For a balanced BST, this is O(\log N); for a skewed BST, it could be O(N).

Summary

By leveraging the in-order traversal of a BST, we can efficiently find the minimum distance between any two nodes with just a single pass through the tree. The key insight is that the smallest difference will always be between two consecutive values in sorted order. This approach is both elegant and efficient, reducing time complexity from quadratic to linear and requiring only minimal extra space.