Minimum Absolute Difference in a BST

Given a binary search tree with at least two nodes and non-negative values, return the minimum absolute difference between the values of any two nodes.

LeetCode: 530. Minimum Absolute Difference in BST

Example

Text

Values inserted: 4, 2, 6, 1, 3

      4
     / \
    2   6         Output: 1   (for example |2 - 1|)
   / \
  1   3

Brute force: every pair

Collect the values and compare every pair. A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. The values are non-negative, so a difference of two values cannot overflow int.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static void collect(TreeNode root, List<Integer> out) {
        if (root == null) return;
        out.add(root.val);
        collect(root.left, out);
        collect(root.right, out);
    }

    static int minDiff(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        collect(root, values);
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < values.size(); i++) {
            for (int j = i + 1; j < values.size(); j++) {
                best = Math.min(best, Math.abs(values.get(i) - values.get(j)));
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(minDiff(fromValues(4, 2, 6, 1, 3)));
        System.out.println(minDiff(fromValues(1, 0, 48, 12, 49)));
    }
}

Output

1
1

Time: O(n²). Space: O(n).

Optimal: in-order, compare neighbours

An in-order traversal of a BST visits the values in sorted order. In a sorted list, the closest pair is always two neighbours: any other pair has a neighbour pair between them with a smaller or equal gap. So compare each value with the one visited immediately before it.

Java passes an int by value, so a method cannot update the caller's int. The code keeps the previous value and the best difference in a small State object that every recursive call shares.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static class State {
        boolean hasPrev = false;
        int prev;
        int best = Integer.MAX_VALUE;
    }

    static void inorder(TreeNode root, State s) {
        if (root == null) return;
        inorder(root.left, s);
        if (s.hasPrev) {
            s.best = Math.min(s.best, root.val - s.prev);
        }
        s.hasPrev = true;
        s.prev = root.val;
        inorder(root.right, s);
    }

    static int minDiff(TreeNode root) {
        State s = new State();
        inorder(root, s);
        return s.best;
    }

    public static void main(String[] args) {
        System.out.println(minDiff(fromValues(4, 2, 6, 1, 3)));
        System.out.println(minDiff(fromValues(1, 0, 48, 12, 49)));
        System.out.println(minDiff(fromValues(10, 20)));
        System.out.println(minDiff(fromValues(5, 8, 5))); // duplicate values: difference 0
    }
}

Output

Time: O(n). Space: O(h) for the recursion.

Values arrive in increasing order, so root.val - s.prev is never negative and no Math.abs is needed.

Edge cases

Two nodes: their difference.
Duplicates: this course's BSTs send equal values to the right, so they are visited next to each other and the answer is 0.
Not a BST: the in-order values are not sorted, and the neighbour argument fails. Sort the values first (O(n log n)).