Skip to main content

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:

  1. In-order Traversal: This will ensure that the nodes are visited in increasing order of their values.
  2. Tracking the Minimum Difference: During the traversal, calculate the difference between each node and its predecessor.
  3. 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:

  1. Base Case: If the current node (root) is NULL, we simply return without doing anything.
  2. 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)).
  3. 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:

  1. 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.

  2. 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

Popular posts from this blog

Top 10 Beginner-Friendly LeetCode Questions and Their Solutions

If you're new to solving coding problems on LeetCode, it can feel overwhelming. Where do you start? Which problems are suitable for beginners? Don’t worry! In this blog post, I’ll guide you through 10 beginner-friendly LeetCode questions that are perfect for getting started on your coding journey. These problems will help you build confidence, improve your problem-solving skills, and lay a solid foundation in data structures and algorithms. Why Start with Beginner-Friendly Problems? Before diving into advanced topics like dynamic programming or graph theory, it’s essential to: Build a strong foundation in basic programming concepts. Understand how to approach a coding problem methodically. Gain familiarity with LeetCode’s platform and its problem structure. The following problems are simple yet impactful, designed to introduce you to common techniques like loops, arrays, strings, and basic math operations. 10 Beginner-Friendly LeetCode Problems 1. Two Sum (Easy) Problem Link : Two...

How to Solve LeetCode’s Hard Problems Without Getting Stuck

LeetCode’s hard problems can seem daunting, especially when you’re just getting comfortable with coding. Tackling these problems isn’t about innate talent—it’s about persistence, learning, and applying the right strategies. In this blog, I’ll share actionable tips and techniques to help you solve LeetCode hard problems without getting stuck and make consistent progress in your problem-solving journey. Why Are Hard Problems Hard? LeetCode hard problems challenge your understanding of advanced data structures, algorithms, and optimization techniques. Here’s why they’re tough: They require deep problem-solving skills and out-of-the-box thinking. Many involve multiple layers of complexity . Edge cases and large inputs often test your algorithm’s efficiency. They push you to master topics like dynamic programming, graph traversal, and segment trees. However, with the right approach, you can break down even the most complex problems into manageable parts. Start with the Right Mindset Appro...

Efficient Solution to LeetCode 2563: Count the Number of Fair Pairs in C++

 his problem tests our understanding of efficient array traversal techniques and highlights the power of binary search when working with sorted arrays. By the end of this post, you’ll have a clear, optimized solution in C++ that avoids Time Limit Exceeded (TLE) errors and uses two-pointer and binary search techniques . Let’s get started by breaking down the problem and exploring a step-by-step approach to a performant solution. Problem Statement Given: An integer array nums of size n . Two integers, lower and upper . Our goal is to count all pairs (i, j) where: 0 <= i < j < n , and lower <= nums[i] + nums[j] <= upper . Example Walkthrough Let's clarify with an example: Example 1 Input: nums = [0, 1, 7, 4, 4, 5] , lower = 3 , upper = 6 Output: 6 Explanation: Valid pairs that satisfy the condition are (0,3) , (0,4) , (0,5) , (1,3) , (1,4) , and (1,5) . Example 2 Input: nums = [1, 7, 9, 2, 5] , lower = 11 , upper = 11 Output: 1 Explanation: There is only one valid p...