# Minimum Absolute Difference in BST
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-absolute-difference-in-bst)
Canonical: https://scaleengineer.com/dsa/problems/minimum-absolute-difference-in-bst
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
Given the `root` of a Binary Search Tree (BST), return _the minimum absolute difference between the values of any two different nodes in the tree_.
**Example 1:**
**Input:** root = [4,2,6,1,3]
**Output:** 1
**Example 2:**
**Input:** root = [1,0,48,null,null,12,49]
**Output:** 1
**Constraints:**
* The number of nodes in the tree is in the range `[2, 104]`.
* `0 <= Node.val <= 105`
**Note:** This question is the same as 783:
# Approaches
## Brute Force Comparison
This naive approach involves collecting all node values from the BST into a list and then comparing every possible pair of values to find the minimum absolute difference.
**Time:** O(N^2), where N is the number of nodes. The tree traversal takes O(N) time. The nested loops to compare all pairs of values take O(N^2) time, which dominates the complexity. · **Space:** O(N), where N is the number of nodes. This space is required to store all the node values in a list. The recursion stack for traversal also contributes, up to O(N) in the worst case of a skewed tree.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient due to the O(N^2) time complexity.; Fails to leverage the ordered nature of a Binary Search Tree.; Requires extra space proportional to the number of nodes.
### Explanation
First, we perform a traversal (like pre-order) of the entire BST to gather all the node values and store them in a list. Then, we use two nested loops to iterate through all unique pairs of values in the list. For each pair `(list[i], list[j])`, we calculate their absolute difference `abs(list[i] - list[j])`. We maintain a variable, `minDifference`, initialized to a very large value. We update this variable whenever we find a smaller difference. After checking all pairs, `minDifference` will hold the minimum absolute difference. This method does not utilize the properties of a BST, making it inefficient for this problem.
```java
import java.util.ArrayList;
import java.util.List;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int getMinimumDifference(TreeNode root) {
List values = new ArrayList<>();
collectValues(root, values);
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < values.size(); i++) {
for (int j = i + 1; j < values.size(); j++) {
minDiff = Math.min(minDiff, Math.abs(values.get(i) - values.get(j)));
}
}
return minDiff;
}
private void collectValues(TreeNode node, List values) {
if (node == null) {
return;
}
values.add(node.val);
collectValues(node.left, values);
collectValues(node.right, values);
}
}
```
### Algorithm
- Create an empty list `values`.
- Define a helper function `collectValues(node, list)` that recursively traverses the tree and adds each node's value to the `list`.
- Call `collectValues(root, values)` to populate the list.
- Initialize `minDiff` to `Integer.MAX_VALUE`.
- Use a nested loop to iterate through all pairs of indices `(i, j)` where `j > i`.
- For each pair, calculate `diff = Math.abs(values.get(i) - values.get(j))`.
- Update `minDiff = Math.min(minDiff, diff)`.
- Return `minDiff`.
## Traversal and Sorting
A more optimized approach is to collect all node values, sort them, and then find the minimum difference between adjacent elements. The minimum difference in a sorted set of numbers will always occur between two consecutive numbers.
**Time:** O(N log N), where N is the number of nodes. The tree traversal takes O(N), sorting the list takes O(N log N), and the final pass takes O(N). The sorting step is the bottleneck. · **Space:** O(N) to store the node values in a list. The recursion stack for traversal also contributes up to O(N) in the worst case.
**Pros:** Significantly more efficient than the brute-force approach.; Relatively easy to implement.
**Cons:** Still not optimal as it requires extra space for the list and an O(N log N) sorting step.; It doesn't fully exploit the BST property in real-time; it uses it indirectly by sorting the collected values.
### Explanation
Similar to the brute-force approach, we first traverse the tree to collect all node values into a list. Any traversal order (pre-order, in-order, or post-order) works for this step. Once we have the list of all values, we sort it in ascending order. After sorting, the problem is reduced to finding the minimum difference between any two adjacent elements in the sorted list. We iterate through the sorted list from the second element and calculate the difference between the current element and the previous one. We keep track of the minimum difference found during this single pass.
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int getMinimumDifference(TreeNode root) {
List values = new ArrayList<>();
collectValues(root, values);
Collections.sort(values);
int minDiff = Integer.MAX_VALUE;
for (int i = 1; i < values.size(); i++) {
minDiff = Math.min(minDiff, values.get(i) - values.get(i - 1));
}
return minDiff;
}
private void collectValues(TreeNode node, List values) {
if (node == null) {
return;
}
values.add(node.val);
collectValues(node.left, values);
collectValues(node.right, values);
}
}
```
### Algorithm
- Create an empty list `values`.
- Traverse the tree (e.g., using pre-order traversal) and add all node values to the `values` list.
- Sort the `values` list using `Collections.sort()`.
- Initialize `minDiff` to `Integer.MAX_VALUE`.
- Iterate through the sorted list from the second element (`i = 1` to `values.size() - 1`).
- In each iteration, calculate the difference: `diff = values.get(i) - values.get(i - 1)`.
- Update `minDiff = Math.min(minDiff, diff)`.
- Return `minDiff`.
## In-order Traversal
The most efficient approach leverages the fundamental property of a BST: an in-order traversal visits the nodes in ascending order of their values. By keeping track of the previously visited node's value, we can find the minimum difference in a single pass.
**Time:** O(N), where N is the number of nodes. We visit each node exactly once during the in-order traversal. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the best case (a balanced tree), H is O(log N). In the worst case (a skewed tree), H is O(N).
**Pros:** Optimal time complexity of O(N).; Space complexity is better than O(N) for balanced trees.; Elegantly uses the core property of a BST.
**Cons:** The recursive implementation can lead to a stack overflow for very deep, skewed trees, although this is unlikely given the problem constraints. An iterative in-order traversal using a stack can mitigate this.
### Explanation
An in-order traversal (Left -> Root -> Right) on a BST processes the nodes in a sorted sequence. This means that the minimum difference between any two nodes must be between two nodes that are adjacent in the in-order traversal sequence. We can perform a recursive in-order traversal. We use a global or member variable `prevValue` to store the value of the previously visited node and `minDifference` to store the minimum difference found so far. The traversal function works as follows:
1. Recursively traverse the left subtree.
2. When visiting the current node, if `prevValue` is not null (i.e., this is not the first node in the traversal), calculate the difference `currentNode.val - prevValue`. Update `minDifference` with this value if it's smaller.
3. Update `prevValue` to the current node's value.
4. Recursively traverse the right subtree.
This way, we compare each node with its immediate predecessor in the sorted sequence, guaranteeing we find the minimum difference without needing to store all values or sort them explicitly.
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Integer prevValue = null;
private int minDifference = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
inOrderTraversal(root);
return minDifference;
}
private void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
// Traverse left subtree
inOrderTraversal(node.left);
// Process current node
if (prevValue != null) {
minDifference = Math.min(minDifference, node.val - prevValue);
}
prevValue = node.val;
// Traverse right subtree
inOrderTraversal(node.right);
}
}
```
### Algorithm
- Initialize two instance variables: `prevValue` to `null` and `minDifference` to `Integer.MAX_VALUE`.
- Define a recursive helper function `inOrderTraversal(node)`.
- Inside the helper function:
- Base case: If `node` is `null`, return.
- Recursively call `inOrderTraversal(node.left)`.
- Process the current node:
- If `prevValue` is not `null`, calculate `node.val - prevValue` and update `minDifference` if this difference is smaller.
- Set `prevValue = node.val`.
- Recursively call `inOrderTraversal(node.right)`.
- Call `inOrderTraversal(root)` from the main function.
- Return `minDifference`.
# Solutions
### Java
```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; private int prev ; private int inf = Integer . MAX_VALUE ; public int getMinimumDifference ( TreeNode root ) { ans = inf ; prev = inf ; dfs ( root ); return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); ans = Math . min ( ans , Math . abs ( root . val - prev )); prev = root . val ; dfs ( root . right ); } }
```
### JavaScript
```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var getMinimumDifference =
function (root) {
let [ans, pre] = [Infinity, -Infinity];
const dfs = (root) => {
if (!root) {
return;
}
dfs(root.left);
ans = Math.min(ans, root.val - pre);
pre = root.val;
dfs(root.right);
};
dfs(root);
return ans;
};
```
### CPP
```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: const int inf = INT_MAX ; int ans ; int prev ; int getMinimumDifference ( TreeNode * root ) { ans = inf , prev = inf ; dfs ( root ); return ans ; } void dfs ( TreeNode * root ) { if ( ! root ) return ; dfs ( root -> left ); ans = min ( ans , abs ( prev - root -> val )); prev = root -> val ; dfs ( root -> right ); } };
```
### Python
```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def getMinimumDifference ( self , root : TreeNode ) -> int : def dfs ( root ): if root is None : return dfs ( root . left ) nonlocal ans , prev ans = min ( ans , abs ( prev - root . val )) prev = root . val dfs ( root . right ) ans = prev = inf dfs ( root ) return ans
```