algoadvance

Leetcode 530. Minimum Absolute Difference in BST

Problem Statement

Given a binary search tree (BST) with distinct values, find the minimum absolute difference between the values of any two nodes in the tree.

Clarifying Questions

  1. Input Constraints:
    • Are the values in the BST all distinct?
      • Yes, the values are distinct.
    • What is the range of the number of nodes in the tree?
      • Typically 1 <= Nodes <= 10^4.
    • Are negative values allowed in the BST?
      • Yes, both negative and positive values are allowed.
    • What should we return if the BST contains only one node?
      • Ideally, this case wouldn’t be given as there are no two nodes to compare. However, we can assume a default return value (e.g., Integer.MAX_VALUE) or not handle it unless specified.

Strategy

  1. In-Order Traversal: Since the BST’s inorder traversal gives nodes in non-decreasing order, the difference between consecutive elements in this traversal will naturally include the minimum absolute difference.
  2. Track Minimum Difference: As we traverse, compare the current node with the previous node and keep track of the smallest difference.
  3. Space & Time Efficiency: Use an iterative approach or recursion with constant extra space apart from the recursion stack to process nodes.

Code

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode prev = null;
        int minDifference = Integer.MAX_VALUE;

        while (!stack.isEmpty() || current != null) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            
            if (prev != null) {
                minDifference = Math.min(minDifference, Math.abs(current.val - prev.val));
            }
            
            prev = current;
            current = current.right;
        }
        
        return minDifference;
    }
}

Explanation

  1. Initialization: Use a stack to simulate the recursive in-order traversal of a BST.
  2. In-Order Traversal: Traverse to the leftmost node and push each node onto the stack until reaching a null reference.
  3. Node Processing: Pop nodes from the stack to process:
    • Compare the current node’s value with the previous node’s value.
    • Update the minimum difference if the current difference is smaller.
    • Move to the right subtree to continue the traversal.
  4. Termination: The process continues until all nodes are traversed and the stack is empty.

Time Complexity

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