Minimum Absolute Difference in BST
Understanding the Problem
We need to find the smallest absolute difference between any two node values in a BST. Comparing every pair of nodes would be O(n^2), but the BST property removes most of that work.
In a BST, an inorder traversal visits nodes in ascending order. In a sorted sequence, the minimum absolute difference always occurs between two adjacent elements, so we only need to compare consecutive nodes in the inorder traversal. The reason is arithmetic: for any sorted triple a < b < c, the gap (c - a) equals (c - b) + (b - a), which is at least as large as either adjacent gap. Skipping over an element can never produce a smaller difference.
Key Constraints:
2 <= number of nodes <= 10^4→ The tree always has at least 2 nodes, so a valid pair always exists. With up to 10,000 nodes, an O(n) traversal is fast.0 <= Node.val <= 10^5→ Values are non-negative and bounded by 10^5, so the largest possible difference is 10^5. This fits in a 32-bit int, and subtracting two values can never overflow.
Approach 1: Inorder Traversal with Array
Intuition
Collect all node values with an inorder traversal, then scan the resulting list comparing each element with its neighbor to find the minimum gap.
An inorder traversal (left, node, right) of a BST visits nodes in ascending order, so the collected list is already sorted without a separate sort step. Once the list is sorted, the minimum absolute difference is the smallest gap between consecutive elements.
Algorithm
- Perform an inorder traversal of the BST and collect all node values into a list.
- Iterate through the list from index 1 to the end.
- At each index, compute the difference between the current element and the previous one.
- Track the minimum difference seen so far.
- Return the minimum difference.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node once during the inorder traversal, and then make one more pass through the list to find the minimum gap. Both steps are O(n).
- Space Complexity: O(n). We store all n node values in a list. The recursion stack also uses O(h) space where h is the tree height, but the list dominates.
Storing every value is unnecessary since we only ever compare adjacent pairs. The next approach keeps a single reference to the previously visited node and computes differences during the traversal itself.
Approach 2: Inorder Traversal with Previous Pointer (Optimal)
Intuition
Instead of collecting all values and scanning afterward, compute each gap during the traversal. The inorder traversal already visits nodes in sorted order, so keeping a reference to the previously visited node lets us compare every consecutive pair as we reach it. Each new node yields one candidate difference (node.val - prev.val), and the running minimum tracks the smallest seen.
This produces the same answer as Approach 1 with the same set of comparisons, but without holding the full list of values in memory.
Algorithm
- Initialize
prevto null andminDiffto infinity (or Integer.MAX_VALUE). - Perform an inorder traversal of the BST.
- At each node, if
previs not null, computenode.val - prev.valand updateminDiffif this is smaller. - Set
prevto the current node before moving on. - After the traversal, return
minDiff.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once during the inorder traversal. At each node, we do O(1) work (one comparison, one assignment).
- Space Complexity: O(h). Where h is the height of the tree. The only space we use is the recursion stack. For a balanced BST, h = O(log n). For a skewed tree, h = O(n) in the worst case.
The time is optimal, but the recursion stack still uses O(h) space. Morris traversal removes the stack entirely and brings the extra space down to O(1).
Approach 3: Morris Inorder Traversal (Space Optimal)
Intuition
Morris traversal performs an inorder traversal with no recursion stack and no explicit stack. It uses the null right pointers that already exist in the tree as temporary "threads" back to ancestor nodes, so it can return upward without storing anything.
The mechanism: before descending into a left subtree, find its rightmost node, which is the inorder predecessor of the current node. Point that node's null right pointer at the current node. After the left subtree is fully traversed, following this thread leads back to the current node, signaling that its left side is done and it can be processed. The thread is then removed.
Each node with a left child is reached exactly twice: once on the way down (when its predecessor's right pointer is null, so we create the thread and go left) and once on the way back up (when its predecessor's right pointer already points to it, so we remove the thread and process the node). A node with no left child is processed immediately and never threaded. The predecessor search walks right pointers that are either real edges or the single thread we created, so it always terminates. Because every thread that is created is later removed, the tree is restored to its original shape, and the processing order is exactly the inorder sequence.
Algorithm
- Initialize
currentto the root,prevto null, andminDiffto infinity. - While
currentis not null: - If
currenthas no left child, processcurrent(compare withprev, updateminDiff), setprev = current, then move tocurrent.right. - If
currenthas a left child, find the inorder predecessor (rightmost node in the left subtree). - If the predecessor's right child is null, set it to
current(create thread), then movecurrenttocurrent.left. - If the predecessor's right child is already
current(thread exists), remove the thread, processcurrent, setprev = current, then move tocurrent.right. - Return
minDiff.
Example Walkthrough
Code
- Time Complexity: O(n). Each node is visited at most twice (once to create the thread, once to remove it), so the total work is still proportional to n.
- Space Complexity: O(1). No recursion stack, no explicit stack, no list. We only use a constant number of pointers. The tree is temporarily modified but restored.