Algorithm
Problem Name: 530. 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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
int minDiff;
TreeNode prev;
public int getMinimumDifference(TreeNode root) {
minDiff = Integer.MAX_VALUE;
prev = null;
helper(root);
return minDiff;
}
private void helper(TreeNode root) {
if (root == null) {
return;
}
helper(root.left);
if (prev != null) {
minDiff = Math.min(minDiff, Math.abs(root.val - prev.val));
}
prev = root;
helper(root.right);
}
}
Input
root = [4,2,6,1,3]
Output
1
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const getMinimumDifference = function(root) {
const arr = [];
traversal(root, arr);
let min = Number.MAX_SAFE_INTEGER;
for (let i = 1; i < arr.length; i++) {
min = Math.min(min, arr[i] - arr[i - 1]);
}
return min;
};
function traversal(node, arr) {
if (node === null) return;
if (node.left) {
traversal(node.left, arr);
}
arr.push(node.val);
if (node.right) {
traversal(node.right, arr);
}
}
Input
root = [4,2,6,1,3]
Output
1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def getMinimumDifference(self, root: TreeNode) -> int:
self.res = sys.maxsize
def dfs(node):
if not node: return sys.maxsize, -sys.maxsize
lMn, lMx = dfs(node.left)
rMn, rMx = dfs(node.right)
self.res = min(self.res, node.val - lMx, rMn - node.val)
return min(node.val, lMn), max(node.val, rMx)
dfs(root)
return self.res
Input
root = [1,0,48,null,null,12,49]
Output
1
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0530_MinimumAbsoluteDifferenceInBST
{
private int answer;
private int prev;
public int GetMinimumDifference(TreeNode root)
{
answer = int.MaxValue;
prev = int.MaxValue;
DFS(root);
return answer;
}
private void DFS(TreeNode node)
{
if (node == null) return;
DFS(node.left);
if (prev != int.MaxValue)
answer = Math.Min(answer, node.val - prev);
prev = node.val;
DFS(node.right);
}
}
}
Input
root = [1,0,48,null,null,12,49]
Output
1