Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The whole problem is one BST insight: an in-order traversal visits nodes in sorted ascending order, and in a sorted sequence the minimum gap must be between two ADJACENT values. So do an in-order DFS, keep a single `prev` pointer to the previously visited value, and at each node update the answer with `node.val − prev`. No need to collect all values — just track the previous one and the running minimum.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you connect 'BST + minimum difference' to 'in-order traversal gives sorted order, so compare adjacent values', rather than brute-forcing all pairs or sorting a collected array.
Where candidates slip
Comparing every pair of nodes O(n²), or computing differences between a node and its parent/children (not the in-order neighbor), which misses the true minimum gap.
How to stand out
State the two-part insight crisply — in-order is sorted, min gap is between adjacents — and implement it with a single prev pointer in O(1) extra space, then mention the iterative-stack variant for the no-recursion follow-up.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:In-order on a BST sorts the values; the smallest gap in a sorted line is always between neighbors.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
In-Order DFS Tracking the Previous Value (Optimal)
1Hint 1Explore hintHide hint
It's a BST. Is there a traversal order that visits the values from smallest to largest?
2Hint 2Explore hintHide hint
In-order traversal of a BST yields sorted values. In a sorted list, where can the minimum difference possibly be?
3Hint 3Explore hintHide hint
Only between adjacent elements. So traverse in-order, remember the previously visited value, and at each node take min(best, node.val − prev).
A · Core idea
This problem is a litmus test for whether you internalize the single most useful BST fact: an in-order traversal (left, node, right) of a binary search tree visits the values in strictly ascending order. Once you see that, the problem nearly solves itself.
Why sorted order collapses the search. The brute-force reading — 'minimum difference between any two nodes' — sounds like it requires examining all O(n²) pairs. But once the values are sorted, a classic fact applies: the minimum absolute difference in a sorted sequence is always between two adjacent elements. Intuitively, if two values are not adjacent, there's at least one value sitting between them, and that in-between value is closer to each of them than they are to each other. So any non-adjacent pair can be beaten by an adjacent one, and we only ever need to compare neighbors.
Why a single `prev` pointer suffices. We don't need to materialize the sorted array at all. As the in-order traversal unfolds, it produces the values one at a time in increasing order. If we remember just the previous value emitted, then at each new node we can compute node.val − prev — the gap to its immediate predecessor in sorted order — and fold it into a running minimum best. After the whole traversal, best holds the global minimum. State is O(1) beyond the call stack: one previous value and one best-so-far.
Why the subtraction needs no absolute value. Because in-order yields ascending values, node.val is always ≥ prev, so node.val − prev is already non-negative — it is the absolute difference. We still guard the very first node: there's no predecessor yet, so we initialize prev to a sentinel (null/None) and skip the comparison until a real previous value exists. Forgetting that guard either crashes on a null prev or pollutes best with a bogus comparison against zero.
Why in-order specifically, not pre/post-order. Pre-order and post-order do not emit BST values in sorted order, so the adjacent-gap argument wouldn't hold for them. The left-node-right sequencing is precisely what aligns the traversal with the sorted order, which is the linchpin of the whole approach. This same template — in-order plus a prev pointer — also detects whether a tree is a valid BST (check prev < node.val) and finds the k-th smallest element, so it's worth committing to muscle memory.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [4,2,6,1,3]Interactive diagram
In-order over [4,2,6,1,3]
visit 1Left→node→right emits 1,2,3,4,6 in sorted order; the minimum neighbor gap (1) is the answer.
1C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
Two facts compose into the answer: (1) in-order on a BST is sorted, and (2) the tightest gap in a sorted list is between neighbors. Combine them and an apparently O(n²) pairwise problem becomes a single O(n) pass with O(1) extra memory. The prev-pointer in-order scan is the BST Swiss-army knife.
ComplexityO(n) time, O(h) space — A single in-order traversal visits each node once with O(1) work → O(n) time. Extra state is just prev and best (O(1)); the recursion stack costs O(h) → O(log n) balanced, O(n) degenerate.
E · Edge cases and pitfalls7root = [1,null,3] — In-order 1,3 → single gap 2 → returns 2. Two-node minimum case.Explore edge casesHide edge cases
Edge cases handled
root = [1,null,3]In-order 1,3 → single gap 2 → returns 2. Two-node minimum case.root = [0,null,100000]In-order 0,100000 → gap 100000; confirms large-value handling within int.Left-skewed BST [5,4,null,3,null,2]In-order 2,3,4,5 → all gaps 1 → returns 1; recursion depth O(n).
Pitfalls
- Using pre-order or post-order, which don't emit sorted values.
- Comparing a node only to its parent/children instead of its in-order neighbor.
- Forgetting the null-prev guard on the first node.
- Collecting all values into a list and sorting — correct but wastes O(n) space and the BST property.
Approach 2 of 2
Iterative In-Order with an Explicit Stack
1Hint 1Explore hintHide hint
Recursion's call stack is what produces the in-order sequence. To go iterative, simulate that stack yourself.
2Hint 2Explore hintHide hint
Push left children until null, then pop a node (that's the next in sorted order), process it, and move to its right child.
3Hint 3Explore hintHide hint
Keep the same prev pointer and best minimum; compare each popped node's value to prev.
A · Core idea
When the interviewer asks for a non-recursive version, or when a degenerate (linked-list-shaped) BST threatens a stack overflow, we make the in-order traversal explicit with our own stack — while keeping the prev/best logic byte-for-byte identical.
Why the stack reproduces in-order. In-order means 'fully explore the left spine before visiting a node, then go right'. The iterative idiom captures this with two moves: from the current node, push it and walk left until there's no left child (stacking the entire left spine); then pop — the popped node is the smallest unvisited value, i.e. the next in sorted order — process it, and set the current pointer to its right child to repeat. This push-left-then-pop-then-go-right dance emits exactly the same ascending sequence the recursion would.
Why the comparison logic is unchanged. Each time we pop a node we have the next sorted value. We compare it to prev exactly as before — best = min(best, node.val − prev) when prev exists — and then set prev to this value. The algorithmic content is identical; only the mechanism that orders the visits has moved from the language runtime's call stack into our explicit one.
Why this guards against deep trees. A BST can degenerate into a chain of n nodes (e.g., values inserted in sorted order), giving a height of n. Recursion would then recurse n deep and risk a stack overflow in languages with limited stack depth. The iterative version uses heap-allocated stack storage, which typically tolerates much larger depths, so it's the safer choice when n is large and the tree might be skewed.
Why the complexity is the same. Every node is pushed once and popped once, so time is O(n). The explicit stack holds at most one root-to-leftmost-leaf path at a time, so its peak size is the height h — identical O(h) space to the recursion, just relocated. There's no asymptotic difference, only the practical robustness of not relying on the call stack.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,0,48,null,null,12,49]push left spine
from 1 push 1, then 0; stack=[1,0]
ready to pop smallest1C · Code with teaching comments
Reference implementation previewpublic int getMinimumDifference(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; Integer prev = null; int best = Integer.MAX_VALUE;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The recursion's implicit call stack and this explicit stack produce the very same in-order sequence; swapping one for the other changes nothing about the prev-pointer logic. Recognizing 'in-order = push the left spine, pop, go right' lets you de-recurse any in-order BST algorithm on demand.
ComplexityO(n) time, O(h) space — Each node is pushed and popped exactly once → O(n) time. The stack holds at most one root-to-leftmost path → O(h) space, matching the recursion.
E · Edge cases and pitfalls7root = [2,1] — Stack yields 1,2 → gap 1 → returns 1.Explore edge casesHide edge cases
Edge cases handled
root = [2,1]Stack yields 1,2 → gap 1 → returns 1.Right-skewed BSTLeft spines are length 1; stack stays shallow, traversal still ascending.Degenerate left chain of 10⁴ nodesExplicit stack avoids recursion-depth overflow; O(h) heap stack handles it.
Pitfalls
- Forgetting to push the left spine before popping, breaking sorted order.
- Not moving to cur.right after popping, skipping right subtrees.
- Reinitializing prev/best inside the loop.
- Comparing with absolute value unnecessarily — values already ascend.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Comparing all pairs instead of adjacent in-order values
Checking every pair is O(n²) and ignores the BST structure. The minimum gap is guaranteed to be between consecutive in-order values, so an O(n) scan suffices.
Explore the code comparisonHide the code comparison
Comparing all pairs instead of adjacent in-order values
Checking every pair is O(n²) and ignores the BST structure. The minimum gap is guaranteed to be between consecutive in-order values, so an O(n) scan suffices.
Don't write this
List<Integer> vals = new ArrayList<>();
collect(root, vals);
int best = Integer.MAX_VALUE;
for (int i = 0; i < vals.size(); i++)
for (int j = i + 1; j < vals.size(); j++)
best = Math.min(best, Math.abs(vals.get(i) - vals.get(j))); // O(n^2)Write this instead
private Integer prev = null;
private int best = Integer.MAX_VALUE;
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev != null) best = Math.min(best, node.val - prev);
prev = node.val;
inorder(node.right);
}2Wrong traversal order
Only in-order emits BST values sorted. Using pre-order means node.val − prev is not an adjacent-in-sorted-order gap, so the computed minimum can be wrong.
Explore the code comparisonHide the code comparison
Wrong traversal order
Only in-order emits BST values sorted. Using pre-order means node.val − prev is not an adjacent-in-sorted-order gap, so the computed minimum can be wrong.
Don't write this
def preorder(node): # WRONG order for a BST
if node is None:
return
if self.prev is not None:
self.best = min(self.best, abs(node.val - self.prev))
self.prev = node.val
preorder(node.left)
preorder(node.right)Write this instead
def inorder(node):
if node is None:
return
inorder(node.left)
if self.prev is not None:
self.best = min(self.best, node.val - self.prev)
self.prev = node.val
inorder(node.right)3Missing the first-node guard
On the very first in-order node there is no predecessor. Comparing against an uninitialized prev (0 or null) either crashes or wrongly seeds best with node.val − 0.
Explore the code comparisonHide the code comparison
Missing the first-node guard
On the very first in-order node there is no predecessor. Comparing against an uninitialized prev (0 or null) either crashes or wrongly seeds best with node.val − 0.
Don't write this
inorder(node.left);
best = Math.min(best, node.val - prev); // prev unset on first node
prev = node.val;Write this instead
inorder(node.left);
if (prev != null) {
best = Math.min(best, node.val - prev);
}
prev = node.val;Revise
Carry the pattern into the interview
Pattern to remember
In-order traversal (sorted order) + track previous value for adjacent gap
Code pattern to memorize
prev = null, best = +inf
inorder(node):
if node is null: return
inorder(node.left)
if prev != null: best = min(best, node.val - prev)
prev = node.val
inorder(node.right)Rules to remember
- 1In-order traversal of a BST yields values in sorted ascending order — this is THE property you exploit.
- 2In a sorted sequence the smallest difference is always between adjacent elements, never far-apart ones.
- 3Track a single
prevvalue; comparenode.val − prev— values are increasing so the gap is non-negative. - 4Initialize
prevto a sentinel (null/None) and only compare once a real previous value exists. - 5No need to store all values — O(1) extra state (prev + best) beyond the recursion stack suffices.
Use this pattern when
- Find a min/closeness statistic over BST values where sorted order helps
- Anything reducible to 'compare adjacent elements in sorted order'
- You can traverse in-order instead of materializing and sorting an array
- Streaming the sorted sequence with O(1) memory between elements
Choose another pattern when
- It's NOT a BST (arbitrary tree) → in-order isn't sorted; collect and sort, or use a different idea
- You need the actual pair, not just the gap → still works, just remember which two
- Need pairwise difference across non-adjacent constraints → may need all values
- Looking for a target sum/closest value to a query → BST search, not adjacent-gap scan
Interview takeaway
Minimum Absolute Difference in BST is a one-line insight wrapped in a traversal: in-order on a BST is sorted, and sorted means the answer lives between neighbors. Carrying a single `prev` pointer turns it into an O(1)-space scan and is the template for every 'adjacent in sorted order' BST problem.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternIn-order traversal of a BST as a sorted stream, scanned with a prev pointer. Recognise it whenever a BST question reduces to comparing adjacent sorted values. The same one-pointer in-order template underlies Validate BST, Kth Smallest, Find Mode, and Minimum Distance Between BST Nodes.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Minimum Distance Between BST NodesComing soonIdentical problem — same in-order prev-pointer scan.
- Kth Smallest Element in a BSTIn-order traversal again — stop at the k-th emitted value.
- Validate Binary Search TreeSame prev-pointer in-order scan, but assert each value strictly exceeds the previous.
- Find Mode in Binary Search TreeComing soonIn-order groups equal values consecutively; count runs with a prev pointer.