530. Minimum Absolute Difference in BST LeetCode Solution
In this guide, you will get 530. Minimum Absolute Difference in BST LeetCode Solution with the best time and space complexity. The solution to Minimum Absolute Difference in BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Absolute Difference in BST
Given the root of a Binary Search Tree (BST), return the minimum absolute 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, 104].
0 <= Node.val <= 105
Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(\log n)
530. Minimum Absolute Difference in BST LeetCode Solution in C++
class Solution {
public:
// Similar to 94. Binary Tree Inorder Traversal
int getMinimumDifference(TreeNode* root) {
int ans = INT_MAX;
int prev = -1;
stack<TreeNode*> stack;
while (root != nullptr || !stack.empty()) {
while (root != nullptr) {
stack.push(root);
root = root->left;
}
root = stack.top(), stack.pop();
if (prev >= 0)
ans = min(ans, root->val - prev);
prev = root->val;
root = root->right;
}
return ans;
}
}; /* code provided by PROGIEZ */
530. Minimum Absolute Difference in BST LeetCode Solution in Java
class Solution {
// Similar to 94. Binary Tree Inorder Traversal
public int getMinimumDifference(TreeNode root) {
int ans = Integer.MAX_VALUE;
int prev = -1;
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (prev >= 0)
ans = Math.min(ans, root.val - prev);
prev = root.val;
root = root.right;
}
return ans;
}
} // code provided by PROGIEZ
530. Minimum Absolute Difference in BST LeetCode Solution in Python
