🎨Now live: Try our Free AI Image Generation Feature

Description
The problem involves finding the minimum absolute difference between values of any two nodes in a Binary Search Tree (BST). Given the properties of a BST, we can leverage an in-order traversal to retrieve node values in a sorted order.
Intuition
The key intuition behind solving this problem is that an in-order traversal of a BST yields node values in ascending order. Thus, the minimum difference will always be found between two consecutive values in this sorted order.
Approach
- In-Order Traversal: - Perform an in-order traversal of the BST to collect the node values in a list. This ensures the values are in ascending order.
- Compute Minimum Difference: - Iterate through the sorted list of values and compute the differences between consecutive elements. - Track the minimum difference encountered during this iteration.
- Edge Cases: - Handle the case where the tree is empty. - Ensure the solution works for trees with only one node or two nodes.
Complexity
Time Complexity:
O(n), where n is the number of nodes in the BST. This is because we perform an in-order traversal of all nodes and then a single pass to compute the minimum difference.
Space Complexity:
O(n) for storing the values of the nodes in a list during the in-order traversal.
Code
C++
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
vector vals;
inOrder(root, vals);
int minDiff = INT_MAX;
for (int i = 1; i < vals.size(); ++i) {
minDiff = min(minDiff, vals[i] - vals[i - 1]);
}
return minDiff;
}
private:
void inOrder(TreeNode* node, vector& vals) {
if (!node) return;
inOrder(node->left, vals);
vals.push_back(node->val);
inOrder(node->right, vals);
}
};
Python
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def inOrder(node: Optional[TreeNode], values: List[int]):
if node is None:
return
inOrder(node.left, values)
values.append(node.val)
inOrder(node.right, values)
values = []
inOrder(root, values)
min_diff = float('inf')
for i in range(1, len(values)):
min_diff = min(min_diff, values[i] - values[i - 1])
return min_diff
Java
class Solution {
public int getMinimumDifference(TreeNode root) {
List values = new ArrayList<>();
inOrder(root, 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 inOrder(TreeNode node, List values) {
if (node == null) return;
inOrder(node.left, values);
values.add(node.val);
inOrder(node.right, values);
}
}
JavaScript
var getMinimumDifference = function (root) {
let min = Number.MAX_VALUE;
if (root === null)
return 0;
let arr = [];
let inOrder = function (root) {
root.left && inOrder(root.left);
arr.push(root.val)
root.right && inOrder(root.right);
}
inOrder(root);
let i = 0;
let j = i + 1;
while (j < arr.length) {
console.log((arr[j] - arr[i]))
min = Math.min(min, (arr[j] - arr[i]))
i++;
j++;
}
return min;
};