algoadvance

Leetcode 783. Minimum Distance Between BST Nodes

Problem Statement

The problem asks you to find the minimum distance between any two nodes in a Binary Search Tree (BST). The distance between two nodes is defined as the absolute difference between their values.

Example:

Input:
    4
   / \
  2   6
 / 
1   3

Output: 1
Explanation: The minimum difference is between node 2 and node 3.

Clarifying Questions

  1. Q: Can the BST have duplicate values? A: No, as per the binary search tree (BST) property, all the values must be unique.

  2. Q: What is the range of values for the nodes? A: Node values are typically within the integer range.

  3. Q: Is the input BST guaranteed to have at least two nodes? A: Yes, there is at least a root and one additional node.

Strategy

To solve this problem, we can leverage the in-order traversal of the BST, which will visit the nodes in ascending order. By traversing the tree in this order, we can compare each node with its previous node to find the minimum difference.

Key steps:

  1. Perform an in-order traversal of the BST.
  2. While traversing, keep track of the previous node’s value.
  3. Calculate the difference between the current node and the previous node.
  4. Update the minimum difference found if the current difference is smaller.

Code

class Solution {
    Integer previous;
    int minDiff;

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

Time Complexity

The time complexity of this solution is O(N), where N is the number of nodes in the BST. This is because we need to visit each node exactly once during the in-order traversal.

The space complexity is O(H), where H is the height of the tree. In the worst case, this could be O(N) for a skewed tree. For a balanced tree, it will be O(log N). This space is used by the implicit stack during the recursion.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI