Minimum Distance Between BST Nodes

EasyBinary Search Tree · In-order · Morris Traversal🧩 Binary Search Tree & In-order LeetCode #783 ↗Updated Oct 30, 2026

Problem

Given the root of a binary search tree, return the smallest difference between the values of any two distinct nodes. The tree is guaranteed to contain at least two nodes.

Inputroot = [4,2,6,1,3]Output1

Inputroot = [90,69,null,49,89,null,52]Output1

Inputroot = [5,1]Output4

2 ≤ nodes ≤ 100 · 0 ≤ Node.val ≤ 10⁵ · Follow-up: O(1) extra space.

Try it yourself

Java

class Solution {
    public int minDiffInBST(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer is the smallest gap between consecutive values in sorted order, and a BST's in-order traversal produces that order. Morris traversal walks in-order using temporary right-pointer threads instead of a stack, so even O(h) space disappears.

PatternBinary Search Tree & In-order

Instinct The tree is a BST? Its in-order walk is a sorted list and every node splits the search space - think "sorted array in tree form", not "visit everything".

Memory hack Left is less, right is more, in-order reads the sorted score - and every node lives inside a (low, high) fence set by its ancestors.

Open the Binary Search Tree & In-order guide →

Approaches

Brute ForceCollect & Sort

Time O(n log n)Space O(n)

Treat the tree as an unordered bag: copy every value into an array, sort it, and take the smallest difference between neighbours. Sorting does the work the BST ordering could have done for free.

Java

public int minDiffInBST(TreeNode root) {
    List<Integer> vals = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) { // any order is fine, we sort afterwards
        TreeNode node = stack.pop();
        vals.add(node.val);
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    Collections.sort(vals);
    int best = Integer.MAX_VALUE;
    for (int i = 1; i < vals.size(); i++) best = Math.min(best, vals.get(i) - vals.get(i - 1));
    return best;
}

Simple and robust, but pays for a sort and an O(n) array.

BetterIterative In-order with a Stack

Time O(n)Space O(h)

Walk in-order with an explicit stack: slide left as far as possible, pop, process, then step right. Values come out ascending, so comparing each popped value with the previous one finds the minimum gap without storing all values.

Java

public int minDiffInBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    int prev = -1, best = Integer.MAX_VALUE; // values are >= 0, so -1 means "none yet"
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (prev >= 0) best = Math.min(best, cur.val - prev);
        prev = cur.val;
        cur = cur.right;
    }
    return best;
}

Linear and list-free; the stack still costs O(h), which is O(n) for a skewed tree.

OptimalMorris In-order Traversal

Time O(n)Space O(1)

Before descending into a left subtree, find its rightmost node (the in-order predecessor) and point its right at the current node — a thread back up. When we arrive through that thread, the left side is finished: remove the thread, process the node, go right. Every edge is walked a constant number of times and the tree ends up unchanged.

Java

public int minDiffInBST(TreeNode root) {
    TreeNode cur = root;
    int prev = -1, best = Integer.MAX_VALUE;
    while (cur != null) {
        if (cur.left == null) {
            if (prev >= 0) best = Math.min(best, cur.val - prev);
            prev = cur.val;
            cur = cur.right; // may follow a thread back up
            continue;
        }
        TreeNode pred = cur.left;
        while (pred.right != null && pred.right != cur) pred = pred.right;
        if (pred.right == null) {
            pred.right = cur; // create thread, then explore the left subtree
            cur = cur.left;
        } else {
            pred.right = null; // left subtree done: remove thread, visit cur
            if (prev >= 0) best = Math.min(best, cur.val - prev);
            prev = cur.val;
            cur = cur.right;
        }
    }
    return best;
}

Answers the follow-up with O(1) space; trickier to write and briefly mutates the tree.

Pro tip

Don't return early from inside a Morris loop — unfinished threads would leave the caller's tree corrupted.

At a glance

Level	Approach	Time	Space
Brute Force	Collect & Sort	`O(n log n)`	`O(n)`
Better	Iterative In-order with a Stack	`O(n)`	`O(h)`
Optimal	Morris In-order Traversal	`O(n)`	`O(1)`

Common pitfalls

Only comparing a node with its children — neighbours in sorted order may be far apart in the tree.
In Morris traversal, forgetting to reset pred.right = null → the tree is left with cycles.
Using prev = 0 as “no value yet” — a node with value 0 is legal.

Interview tips

Recognise it as the same problem as Minimum Absolute Difference in BST (530).
Walk from sort-based O(n log n) to in-order O(n) to Morris O(1) and justify each step.
When presenting Morris, draw one thread being created and later removed.

Pattern

Morris / threaded in-order → when an in-order BST pass must run in O(1) extra space.

My notes saved in this browser