Minimum Absolute Difference in BST

Given the root of a binary search tree, return the minimum absolute difference between values of any two nodes.

Why this is worth learning

In a sorted sequence, a closest pair is adjacent. The BST supplies that sequence through inorder traversal, so only the previous value must be retained.

Before coding: one-minute experiment

For inorder values [-5,-1,4,10], which pair gives the answer?

Function signature

func MinDiffInBST(root *TreeNode) int

Inputs / outputs

• root: root of the BST.
• Return: minimum absolute difference between any two values.

Example

    4
   / \
  2   6
 / \
1   3
Output: 1

Constraints

• 2 <= number of nodes <= 100_000
• node values fit in 32-bit signed int

Core idea (near-solution)

All-pairs comparison is a correct O(n²) baseline. Ordering lets us discard most pairs: for sorted a≤b≤c, c−a=(b−a)+(c−b), so the outer pair cannot beat both intervening gaps. A minimum pair can therefore be found among adjacent values. A valid BST supplies sorted inorder directly; keep only the previous value and best gap. Use a separate flag for whether a previous value exists rather than inventing a sentinel node value. Values fitting 32 bits do not guarantee their difference fits 32 bits.

Invariant: as you traverse inorder, prev holds the last visited value, and the best answer is the minimum of consecutive differences so far.

Algorithm (step-by-step)

1. Perform iterative inorder with a stack.
2. Track the previous value once you visit the first node.
3. For each new node, update ans = min(ans, node.Val - prev) and update prev.
4. Return ans after traversal.

Correctness sketch

For any sorted values a<=b<=c, c-a=(b-a)+(c-b) is at least each adjacent gap. Thus a nonadjacent pair cannot improve on all gaps between its endpoints; some minimum pair is adjacent in sorted order. Inorder traversal of the valid BST visits values in that order. After the first visit, compare every new value with the previous one and keep the smallest gap. A separate previous-present flag avoids inventing a comparison before the first value. Every adjacent pair is considered exactly once, so the final minimum is the global minimum difference.

Trace (hand walkthrough)

Example input:
    4
   / \
  2   6
 / \
1   3
Output: 1

Walk:
- inorder sequence: 1,2,3,4,6
- diffs: 1,1,1,2 -> min=1

Pitfalls to avoid

• Computing differences without inorder traversal (BST property required).
• Using an uninitialized prev value.

Debugging lens

Test negative values and the two 32-bit endpoints; their difference can exceed signed 32-bit even though each node value fits it. The published at-least-two-nodes precondition makes a minimum pair exist.

Complexity

• Time: O(n)
• Extra space: O(h) for the stack.

Implementation notes (Go)

• Inorder traversal yields sorted values; track prev to compute diffs.
• Initialize prev with a flag so the first node is skipped.

Contract precision

The input is a valid BST with at least two nodes. For the full signed 32-bit node-value domain, the difference can be 4294967295, requiring a 64-bit int target.

Reconstruction checkpoint

For sorted values [−8,−2,7,11], prove why comparing −8 directly with 7 cannot improve the current best adjacent gap. What must change if the input is an arbitrary binary tree?

Return to Binary Search Tree · Module quiz