712351. Minimum Absolute Difference In BST
Minimum Absolute Difference In BST
Summary
Given a Binary Search Tree (BST) and its root node, find the minimum absolute difference between two nodes in the tree. The tree is represented as a node structure where each node contains an integer value and pointers to its left and right children.
Detailed Explanation
To solve this problem, we can start by traversing the BST in ascending order, which allows us to keep track of the previous node's value. We then iterate through the nodes, calculating the absolute difference between the current node's value and the previous node's value. The minimum difference found is the result.
Here's a step-by-step breakdown of the solution:
- Traverse the BST in ascending order using an in-order traversal (left-root-right).
- Initialize a variable
prev_node_valueto hold the value of the previous node. - Iterate through the nodes, starting from the root:
- For each node, calculate the absolute difference between its value and
prev_node_value. - Update
prev_node_valuewith the current node's value. - Keep track of the minimum absolute difference found so far.
- For each node, calculate the absolute difference between its value and
- Return the minimum absolute difference found.
Time complexity: O(n), where n is the number of nodes in the BST, since we visit each node once during the traversal and calculation.
Space complexity: O(1), as we only use a constant amount of space to store the prev_node_value variable and the minimum absolute difference.
Optimized Solutions
Java
public class MinimumAbsoluteDifference {
public static int findMinimumAbsoluteDifference(Node root) {
if (root == null) return 0;
Node prev = null;
int minDiff = Integer.MAX_VALUE;
inOrderTraversal(root, prev, minDiff);
return minDiff;
}
private static void inOrderTraversal(Node node, Node prev, int[] minDiff) {
if (node == null) return;
inOrderTraversal(node.left, node, minDiff);
if (prev != null) {
int diff = Math.abs(node.val - prev.val);
if (diff < minDiff[0]) {
minDiff[0] = diff;
}
}
prev = node;
inOrderTraversal(node.right, prev, minDiff);
}
public static class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
}
}
}