Minimum Absolute Difference in BST
Last Updated: March 29, 2026
Understanding the Problem
We need to find the smallest absolute difference between any two node values in a BST. At first glance, this might seem like we need to compare every pair of nodes, but the BST property gives us a huge shortcut.
In a BST, the inorder traversal visits nodes in sorted (ascending) order. And here is the critical observation: in a sorted sequence, the minimum absolute difference always occurs between two adjacent elements. You would never find a smaller gap by comparing elements that are further apart in the sorted order. So instead of comparing all pairs, we just need to compare consecutive nodes in the inorder traversal.
Key Constraints:
2 <= number of nodes <= 10^4→ The tree always has at least 2 nodes, so there is always a valid pair to compare. With up to 10,000 nodes, O(n) solutions are comfortable and even O(n log n) is fine.0 <= Node.val <= 10^5→ Values are non-negative integers, so no overflow concerns. The maximum possible difference is 10^5, which fits easily in an int.
Approach 1: Inorder Traversal with Array
Intuition
The most natural approach for a beginner: collect all node values via inorder traversal, then scan through the resulting sorted list to find the minimum gap between consecutive elements.
Why inorder? Because in a BST, an inorder traversal (left, node, right) visits nodes in ascending order. That gives us a sorted array without any sorting step. And once we have a sorted array, finding the minimum absolute difference is trivial: just compare each element with its neighbor.
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.
This approach works but stores every value when we only ever compare adjacent pairs. What if we tracked just the previous node during traversal and computed differences on the fly?
Approach 2: Inorder Traversal with Previous Pointer (Optimal)
Intuition
Instead of collecting all values into a list and then scanning for the minimum gap, we can compute the gap as we go. During the inorder traversal, we keep a reference to the previously visited node. Each time we visit a new node, we compute the difference between it and the previous node, and update our running minimum.
This is the same logic as Approach 1, just without the intermediate list. We are streaming through the sorted sequence and computing the answer in real time.
The BST's inorder traversal produces values in sorted order. In any sorted sequence, the minimum absolute difference must occur between two consecutive elements. If you have three sorted values a < b < c, then (c - a) = (c - b) + (b - a), which means (c - a) is always larger than both (c - b) and (b - a). So skipping elements never gives you a smaller gap. By tracking just the previous node, we check every consecutive pair exactly once.
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 uses O(h) space. Can we eliminate the stack entirely using Morris traversal for true O(1) space?
Approach 3: Morris Inorder Traversal (Space Optimal)
Intuition
Morris traversal is a clever technique that lets us do an inorder traversal without any extra space: no recursion stack, no explicit stack, nothing. It temporarily modifies the tree structure by creating "threaded" links from each node's inorder predecessor back to the node itself, which lets us return to parent nodes without a stack.
The core idea: before going left, find the rightmost node in the left subtree (the inorder predecessor). Make a temporary link from that node back to the current node. When we later follow this link back, we know we have finished the left subtree and can process the current node.
Morris traversal exploits the fact that leaf nodes and rightmost nodes in subtrees have null right pointers. We temporarily repurpose these null pointers as "threads" that point back to the inorder successor. This lets us return to ancestor nodes without a stack. Every node gets visited at most twice: once when we first arrive and go left, and once when we come back via the thread. The threads are always cleaned up, so the tree is restored to its original structure when we are done.
Algorithm
- Initialize
currentto the root,prevto null, andminDiffto infinity. - While
currentis not null:
a. If current has no left child, process current (compare with prev, update minDiff), set prev = current, then move to current.right.
b. If current has 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.