Minimum Absolute Difference in BST

Problem Statement

In the given problem, we are provided with the root of a Binary Search Tree (BST) and are required to compute the minimum absolute difference between the values of any two different nodes within the tree. The task is to efficiently navigate through the BST, which inherently has its elements sorted according to BST properties, and find the smallest absolute difference possible between any pair of nodes.

Examples

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

Approach and Intuition

How to Solve the Problem:

1. Understanding BST Properties:

   • In a Binary Search Tree, for any given node, the left subtree contains only nodes with values lesser than the node's value, and the right subtree only nodes with values greater.
   • This property provides a natural sorting of elements which can be leveraged by using in-order traversal to access the nodes in sorted order.

2. Utilizing In-order Traversal:

   • By performing an in-order traversal on the BST, we retrieve the node values in non-decreasing order.
   • This means that the smallest absolute difference will be between consecutive elements in this traversal order.

3. Calculating Minimum Difference:

   • While performing in-order traversal, keep track of the previous node value.
   • For each current node during the traversal, calculate the difference between the current node value and the previous node value.
   • Update the minimum difference found so far with this calculated difference if it's smaller.

Examples and Application:

• From Example 1:
  • The in-order traversal of the tree [4, 2, 6, 1, 3] yields the values [1, 2, 3, 4, 6].
  • The smallest difference here is between consecutive values 3 and 4 (or 1 and 2, or 2 and 3), each providing a difference of 1.
• From Example 2:
  • The in-order traversal of the tree [1, 0, 48, null, null, 12, 49] results in [0, 1, 12, 48, 49].
  • Again, 1 - 0 and 49 - 48 each provide the smallest difference, which is 1.

Constraints to consider:

• The tree will have at least two nodes, guaranteeing that there is at least one valid answer.
• Node values are non-negative and can be quite large, up to 105, but this should not affect the algorithm since only differences are taken into account.

Using the above approach provides a direct and efficient method leveraging the properties of in-order traversal in a BST to find the minimum absolute difference between any two nodes in the tree. This solution operates in O(n) time complexity since each node is visited precisely once during the in-order traversal.

Solutions

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;
    }
};