# Minimum Distance Between BST Nodes
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-distance-between-bst-nodes)
Canonical: https://scaleengineer.com/dsa/problems/minimum-distance-between-bst-nodes
**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
**Companies:** [Wix](https://scaleengineer.com/companies/wix)
---
## Problem
Given the `root` of a Binary Search Tree (BST), return _the minimum 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, 100]`.
* `0 <= Node.val <= 105`
**Note:** This question is the same as 530:
# Approaches
## Brute Force by Comparing All Pairs
This approach involves iterating through all possible pairs of nodes in the tree, calculating the absolute difference of their values, and keeping track of the minimum difference found. It does not utilize the properties of a Binary Search Tree.
**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. Thus, the overall time complexity is dominated by the nested loops. · **Space:** O(N). We need O(N) space to store the node values in a list. The recursion stack for the traversal also uses space, up to O(N) in the case of a skewed tree.
**Pros:** Simple to understand and implement.; Works for any binary tree, not just a BST.
**Cons:** Highly inefficient due to the O(N^2) time complexity.; Fails to leverage the crucial property of the input being a Binary Search Tree.
### Explanation
First, we traverse the entire tree to collect all node values into a list. Any traversal method (pre-order, in-order, post-order) works for this step. After populating the list, we use two nested loops to consider every unique pair of values `(values[i], values[j])`. For each pair, we calculate the absolute difference `abs(values[i] - values[j])`. We maintain a variable, `minDifference`, initialized to a very large value. This variable is updated whenever a smaller difference is found. After checking all pairs, `minDifference` will hold the minimum difference between any two nodes.
```java
import java.util.ArrayList;
import java.util.List;
class Solution {
public int minDiffInBST(TreeNode root) {
List values = new ArrayList<>();
collectValues(root, values);
int minDifference = Integer.MAX_VALUE;
for (int i = 0; i < values.size(); i++) {
for (int j = i + 1; j < values.size(); j++) {
minDifference = Math.min(minDifference, Math.abs(values.get(i) - values.get(j)));
}
}
return minDifference;
}
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` that performs a pre-order traversal of the tree and adds each node's value to the `values` list.
* Call `collectValues` starting from the `root`.
* Initialize `minDifference` to `Integer.MAX_VALUE`.
* Use a nested loop to iterate through all pairs of elements in the `values` list.
* For each pair, calculate the absolute difference and update `minDifference` if the new difference is smaller.
* Return `minDifference`.
## In-order Traversal to Get Sorted Values
This approach leverages the fundamental property of a Binary Search Tree (BST): an in-order traversal visits the nodes in ascending order of their values. By performing an in-order traversal and storing the values in a list, we get a sorted list of all node values. The minimum difference must then occur between two adjacent elements in this sorted list.
**Time:** O(N), where N is the number of nodes. The in-order traversal takes O(N) time to visit every node. The subsequent loop to find the minimum difference in the list also takes O(N) time. · **Space:** O(N). We need O(N) space to store the node values in the list. Additionally, the recursion stack for the in-order traversal uses space proportional to the height of the tree, which can be O(N) in the worst case (a skewed tree).
**Pros:** Much more efficient than the brute-force approach.; Correctly utilizes the BST property.
**Cons:** Requires O(N) extra space to store all the node values, which can be optimized.
### Explanation
We first perform a standard recursive in-order traversal of the BST. During the traversal, we add each node's value to a list. Since it's an in-order traversal on a BST, the list will automatically be sorted in non-decreasing order. After the traversal is complete, we iterate through the sorted list from the second element. In each iteration, we calculate the difference between the current element and the previous element. We keep track of the minimum difference found during this iteration. The final result is the minimum difference found among all adjacent pairs.
```java
import java.util.ArrayList;
import java.util.List;
class Solution {
public int minDiffInBST(TreeNode root) {
List sortedValues = new ArrayList<>();
inOrderTraversal(root, sortedValues);
int minDifference = Integer.MAX_VALUE;
for (int i = 1; i < sortedValues.size(); i++) {
minDifference = Math.min(minDifference, sortedValues.get(i) - sortedValues.get(i - 1));
}
return minDifference;
}
private void inOrderTraversal(TreeNode node, List values) {
if (node == null) {
return;
}
inOrderTraversal(node.left, values);
values.add(node.val);
inOrderTraversal(node.right, values);
}
}
```
### Algorithm
* Create an empty list `sortedValues`.
* Implement a recursive `inOrderTraversal` helper function that traverses the tree in-order and appends each node's value to the `sortedValues` list.
* Call `inOrderTraversal` starting from the `root`.
* Initialize `minDifference` to `Integer.MAX_VALUE`.
* Iterate through the `sortedValues` list from the second element (`i=1`) to the end.
* In each step, calculate `sortedValues.get(i) - sortedValues.get(i - 1)` and update `minDifference` if this new difference is smaller.
* Return `minDifference`.
## Space-Optimized In-order Traversal
This is the most efficient approach. It builds upon the in-order traversal idea but optimizes the space complexity. Instead of storing all the node values in a list, we only need to keep track of the value of the previously visited node in the in-order sequence.
**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 a balanced BST, H is O(log N), and in the worst case of a skewed tree, H is O(N). This is an improvement over the O(N) space required by the list in the previous approach.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(H) for the recursive approach. It avoids storing all N node values.
**Cons:** The recursive implementation can lead to a stack overflow for very deep trees, although the problem constraints (N <= 100) make this unlikely. An iterative in-order traversal using a stack can be used to avoid this, which would still have O(H) space complexity.
### Explanation
The core idea remains the same: the minimum difference will be between two nodes that are adjacent in the sorted order of values. In-order traversal gives us this order. We can perform an in-order traversal and maintain two global or class-level variables: `minDifference` and `prevNodeValue`. `minDifference` is initialized to `Integer.MAX_VALUE`, and `prevNodeValue` is initialized to a state indicating it hasn't been set yet (e.g., `null` or a sentinel value). During the in-order traversal (Left -> Process -> Right): When we process the current node, we first check if `prevNodeValue` has been set. If it has, we calculate the difference between the current node's value and `prevNodeValue`. We then update `minDifference` with the minimum of its current value and this new difference. After processing, we update `prevNodeValue` to the current node's value. This sets it up for the next node in the in-order sequence. This way, we compare each node with its immediate predecessor in the sorted sequence without storing the entire sequence.
```java
class Solution {
private Integer prevNodeValue = null;
private int minDifference = Integer.MAX_VALUE;
public int minDiffInBST(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 (prevNodeValue != null) {
minDifference = Math.min(minDifference, node.val - prevNodeValue);
}
prevNodeValue = node.val;
// Traverse right subtree
inOrderTraversal(node.right);
}
}
```
### Algorithm
* Initialize two instance variables: `minDifference = Integer.MAX_VALUE` and `prevNodeValue = null`.
* Define a recursive `inOrderTraversal` helper function.
* Inside the helper function, for a given `node`:
a. If `node` is `null`, return.
b. Recursively call `inOrderTraversal` on `node.left`.
c. Process the current node:
i. If `prevNodeValue` is not `null`, calculate `node.val - prevNodeValue` and update `minDifference = Math.min(minDifference, node.val - prevNodeValue)`.
ii. Update `prevNodeValue = node.val`.
d. Recursively call `inOrderTraversal` on `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 minDiffInBST ( 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
var minDiffInBST = function ( root ) { let ans = Number . MAX_SAFE_INTEGER , prev = Number . MAX_SAFE_INTEGER ; const dfs = root => { if ( ! root ) { return ; } dfs ( root . left ); ans = Math . min ( ans , Math . abs ( root . val - prev )); prev = 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 minDiffInBST ( 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 minDiffInBST ( self , root : Optional [ 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
```