Minimum Distance Between BST Nodes

easy tree bst dfs

Problem

Given the root of a BST, return the minimum difference between the values of any two different nodes. Because the values are unique, this is the smallest gap among consecutive values in sorted order.

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

Output1

Sorted in-order: 1,2,3,4,6. Smallest consecutive gap is 1.

BST (level-order, "null" for empty)

def min_diff_in_bst(root):
    prev, best = None, float("inf")
    def inorder(node):
        nonlocal prev, best
        if not node: return
        inorder(node.left)
        if prev is not None:
            best = min(best, node.val - prev)
        prev = node.val
        inorder(node.right)
    inorder(root)
    return best

function minDiffInBST(root) {
  let prev = null, best = Infinity;
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (prev !== null) best = Math.min(best, node.val - prev);
    prev = node.val;
    inorder(node.right);
  }
  inorder(root);
  return best;
}

class Solution {
    Integer prev = null;
    int best = Integer.MAX_VALUE;
    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return best;
    }
    void inorder(TreeNode n) {
        if (n == null) return;
        inorder(n.left);
        if (prev != null) best = Math.min(best, n.val - prev);
        prev = n.val;
        inorder(n.right);
    }
}

class Solution {
    int prev = -1, best = INT_MAX;
public:
    int minDiffInBST(TreeNode* root) { inorder(root); return best; }
    void inorder(TreeNode* n) {
        if (!n) return;
        inorder(n->left);
        if (prev != -1) best = min(best, n->val - prev);
        prev = n->val;
        inorder(n->right);
    }
};

Explanation

This is the classic BST in-order trick: because a binary search tree is already organized by value, reading it in-order hands you the numbers in sorted order for free.

The smallest difference between any two node values must come from two values that sit right next to each other once sorted. Two far-apart values can never have a gap smaller than two adjacent ones, so we only compare neighbors.

The code does an in-order walk (inorder(node.left), process node, inorder(node.right)) and keeps just one extra value, prev, the last value seen. At each node it updates best = min(best, node.val - prev).

Example: for [4,2,6,1,3] the in-order sequence is 1, 2, 3, 4, 6. The consecutive gaps are all 1 except the last gap of 2, so the answer is 1.

One pass, one running minimum, no extra sorting needed — the tree's structure already did the sorting for us.

Time: O(n) Space: O(h) recursion