530. Minimum Absolute Difference in BST
Explanation
To find the minimum absolute difference in a Binary Search Tree (BST), we can perform an in-order traversal of the tree which will give us the nodes in sorted order. During the traversal, we can compare adjacent nodes to find the minimum absolute difference.
- Perform an in-order traversal of the BST to get the nodes in sorted order.
- Keep track of the previous node value during the traversal and calculate the absolute difference with the current node value.
- Update the minimum absolute difference if a smaller difference is found.
- Return the minimum absolute difference at the end.
Time Complexity: O(n) - where n is the number of nodes in the BST Space Complexity: O(h) - where h is the height of the BST
class Solution {
int minDiff = Integer.MAX_VALUE;
Integer prev = null;
public int getMinimumDifference(TreeNode root) {
inorder(root);
return minDiff;
}
private void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
if (prev != null) {
minDiff = Math.min(minDiff, root.val - prev);
}
prev = root.val;
inorder(root.right);
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.