Dare2Solve
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.
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.
In-Order Traversal:
Compute Minimum Difference:
Edge Cases:
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.
O(n) for storing the values of the nodes in a list during the in-order traversal.
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
vector<int> 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<int>& vals) {
if (!node) return;
inOrder(node->left, vals);
vals.push_back(node->val);
inOrder(node->right, vals);
}
};
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
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> 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<Integer> values) {
if (node == null) return;
inOrder(node.left, values);
values.add(node.val);
inOrder(node.right, values);
}
}
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;
};