Minimum Absolute Difference In BST

Problem Overview

Inorder traversal of a BST visits values in sorted order.

Intuition

Inorder traversal of a BST visits values in sorted order. The smallest absolute gap in a sorted list always sits between two neighbors, so you only need consecutive inorder values.

Algorithm

1Walk the tree inorder with a recursive DFS.
2Keep the previously visited value, initially unset.
3At each node after the left subtree, if a previous value exists, update the answer with node.data minus previous.
4Set previous to the current node value and recurse on the right subtree.
5Return the running minimum after the traversal finishes.

Example Walkthrough

Input: BST inorder sequence 1, 3, 6

1. Gap 3-1 equals 2.
2. Gap 6-3 equals 3.
3. The minimum is 2.

Output: 2

Common Pitfalls

• Do not compare non-adjacent values; sorted order makes that unnecessary.
• Skip the first node when updating because it has no previous neighbor.
• Storing the full inorder list wastes space; one previous integer is enough.
• Because inorder is nondecreasing, subtraction without abs is safe for the gap.

Minimum Absolute Difference In BST.java

Java

// Approach: BST inorder is sorted, so the minimum absolute difference is
// between some consecutive values. Walk inorder while keeping the previous
// value and update the running minimum; no need to store the full sequence.
// Complexity: O(n) time, O(h) space for the recursion stack.
class Solution {
    private Integer prev;
    private int ans;

    public int absDiff(Node root) {
        prev = null;
        ans = Integer.MAX_VALUE;
        inOrder(root);
        return ans;
    }

    private void inOrder(Node root) {
        if (root == null)
            return;
        inOrder(root.left);
        if (prev != null)
            ans = Math.min(ans, root.data - prev);
        prev = root.data;
        inOrder(root.right);
    }
}

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
    }
}

Was this solution helpful?