How to Find the Minimum Distance Between Nodes in a Binary Search Tree (BST)

How to Find the Minimum Distance Between Nodes in a Binary Search Tree (BST) – Optimized Solution Explained

In a Binary Search Tree (BST), finding the minimum absolute difference between the values of any two distinct nodes is a classic problem in tree data structure algorithms. This problem is a natural extension of the concept of BST properties and is useful in scenarios such as range queries, nearest neighbor searches, and optimization problems.

In this blog post, we’ll walk through the approach to solve the problem of finding the minimum distance between two nodes in a BST. We will break down the solution, discuss different strategies, and demonstrate an optimized approach to solve the problem efficiently.

Problem Statement: Minimum Distance Between BST Nodes (LeetCode Problem 783)

Problem Description:

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

For example:

Input 1:
```
root = [4, 2, 6, 1, 3]
Output: 1
```
The nodes with values 2 and 3 have the smallest absolute difference, which is 1.
Input 2:
```
root = [1, 0, 48, null, null, 12, 49]
Output: 1
```
The nodes with values 0 and 1 have the smallest absolute difference, which is 1.

Exploiting the BST Property

The main insight here is to exploit the properties of the Binary Search Tree (BST). In a BST:

The left subtree contains values less than the current node's value.
The right subtree contains values greater than the current node's value.

This property ensures that an in-order traversal of the tree will yield values in sorted order. Since the nodes are sorted, the smallest absolute difference will always occur between adjacent nodes in the sorted order.

Thus, instead of comparing every pair of nodes, which would be inefficient, we can compute the minimum difference by performing an in-order traversal of the BST and checking the difference between each adjacent pair of nodes.

Approach and Solution Explanation

To solve the problem efficiently, we’ll use an in-order traversal to visit the nodes of the tree in sorted order. We keep track of the previous node’s value during the traversal. By comparing the current node's value with the previous node's value, we can compute the difference and keep track of the smallest difference encountered.

Solution Outline:

In-order Traversal: This will ensure that the nodes are visited in increasing order of their values.
Tracking the Minimum Difference: During the traversal, calculate the difference between each node and its predecessor.
Edge Case Handling: If the tree is empty or has only one node, return an appropriate result (though the problem guarantees at least two nodes).

Code Implementation

Here’s the optimized code to solve the problem:

class Solution {
public:
    int mini = INT_MAX;  // Variable to store the minimum difference
    int pre = -1;        // Variable to store the value of the previous node during traversal

    void solve(TreeNode* root) 
    {
        if (!root) return;  // Base case: if the root is null, return

        // Traverse the left subtree first (LNR order)
        solve(root->left);

        // Process the current node
        if (pre != -1) 
        {
            mini = min(mini, root->val - pre);  // Calculate and update the minimum difference
        }
        pre = root->val;  // Update the previous node's value to the current node's value

        // Traverse the right subtree
        solve(root->right);
    }

    int minDiffInBST(TreeNode* root) 
    {
        solve(root);  // Start the in-order traversal
        return mini;  // Return the minimum difference found
    }
};

Explanation of the Code:

Base Case: If the current node (root) is NULL, we simply return without doing anything.
In-order Traversal:
- First, we recursively visit the left subtree (solve(root->left)).
- We then process the current node. If this is not the first node (i.e., pre != -1), we compute the absolute difference between the current node's value and the previous node's value (pre). We update the mini variable to keep track of the smallest difference.
- Finally, we update pre to the current node's value and recursively visit the right subtree (solve(root->right)).
Return: After completing the in-order traversal, the mini variable will contain the minimum absolute difference between any two nodes in the BST, which we then return.

Time and Space Complexity:

Time Complexity: O(n), where n is the number of nodes in the BST. We visit each node exactly once during the in-order traversal.
Space Complexity: O(h), where h is the height of the tree. This is the space used by the recursion stack. In the worst case, for an unbalanced tree, the space complexity could be O(n), but in the best case (a balanced tree), it is O(log n).

Why This Solution is Efficient:

Single Pass: The solution uses a single in-order traversal to visit each node exactly once. This ensures that we are working in O(n) time complexity, which is the best possible for this problem, as we must visit each node to calculate the minimum difference.
No Extra Space: We only use a few integer variables (mini, pre) to keep track of the minimum difference and the previous node’s value. This makes the space complexity O(h), where h is the height of the tree, which is much more efficient than using extra data structures like arrays or lists.

In this blog post, we’ve walked through the problem of finding the minimum distance between nodes in a BST and discussed how to optimize the solution using an in-order traversal. The key insight is that by visiting the nodes in sorted order, the smallest differences will always be between adjacent nodes.

The optimized solution works in O(n) time and O(h) space, making it both time and space efficient. This approach is optimal for this problem and can be applied to other BST-related problems as well.

SEO Tags:

Minimum Distance Between BST Nodes
Leetcode 783 Solution
Binary Search Tree minimum difference
BST in-order traversal
Finding minimum difference in BST
Leetcode BST problems
Optimized BST search solution

Code With Me

Search This Blog