DSA problem
Minimum Distance Between BST Nodes
Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
The brute-force idea is to collect every node value, sort them, and scan adjacent pairs — but that wastes the BST's defining property. The key observation is that an inorder traversal of a BST yields its values in strictly ascending order. The minimum difference between any two values must therefore occur between some pair of values that are adjacent in that sorted sequence; non-adjacent pairs can only be farther apart.
The optimal approach performs an inorder traversal while remembering only the immediately preceding visited value in a single variable prev. Each time we visit a node we compute curr.val - prev, update the running minimum, and then advance prev to curr.val. This avoids materializing the entire sorted list and is the cleanest expression of the idea.
The traversal can be written recursively or iteratively with a stack. Both touch each node once for O(n) time. The recursive version uses O(h) call-stack space; the iterative version uses O(h) explicit-stack space. Either way, we do not need an O(n) auxiliary array.
Examples
root = [4,2,6,1,3]1root = [1,0,48,null,null,12,49]1root = [90,69,null,49,89,null,52]1Constraints
- The number of nodes in the tree is in the range [2, 100].
- 0 <= Node.val <= 10^5
- The tree is guaranteed to be a valid BST.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.