Minimum Absolute Difference in BST

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

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)

Inorder traversal of a BST yields values in sorted order. The minimum absolute difference must occur between consecutive values in this order.

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

• Invariant: as you traverse inorder, prev holds the last visited value, and the best answer is the minimum of consecutive differences so far.
• Inorder traversal of a BST yields values in sorted order.
• The stack simulates inorder traversal without recursion.
• Thus each popped node is the next smallest element.

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.

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.