Algorithm
Problem Name: 783. Minimum Distance Between BST Nodes
Given the root of a Binary Search Tree (BST), return the minimum 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, 100]. 0 <= Node.val <= 105
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
// Recursive
class Solution {
public:
int minDiffInBST(TreeNode* root) {
int minDiff = INT_MAX;
TreeNode* pre = NULL;
DFS(root, pre, minDiff);
return minDiff;
}
void DFS(TreeNode* root, TreeNode*& pre, int& minDiff){
if(!root) return;
DFS(root->left, pre, minDiff);
if(pre) minDiff = min(minDiff, abs(root->val - pre->val));
pre = root;
DFS(root->right, pre, minDiff);
}
};
// Non-recursive
class Solution {
public:
int minDiffInBST(TreeNode* root) {
int minDiff = INT_MAX;
stack < TreeNode*>s;
TreeNode* p = root, *pre = NULL;
while(!s.empty() || p){
while(p){
s.push(p);
p = p->left;
}
if(pre) minDiff = min(minDiff, abs(s.top()->val - pre->val));
pre = s.top();
s.pop();
p = pre->right;
}
return minDiff;
}
};
Input
root = [4,2,6,1,3]
Output
1
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
Integer minDiff;
Integer prev;
public int minDiffInBST(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, root.val - prev);
}
prev = root.val;
helper(root.right);
}
}
Input
root = [4,2,6,1,3]
Output
1
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const minDiffInBST = function(root) {
if (root === null) return 0;
let min = Number.MAX_SAFE_INTEGER,
res = [];
const bst = (node, res) => {
if (!node) return;
bst(node.left, res);
res.push(node.val);
bst(node.right, res);
};
bst(root, res);
for (let i = 1; i < res.length; i++) {
min = Math.min(min, res[i] - res[i - 1]);
}
return min;
};
Input
root = [1,0,48,null,null,12,49]
Output
1
#4 Code Example with Javascript Programming
Code -
Javascript Programming
class Solution:
def minDiffInBST(self, root):
def dfs(node):
if not node: return float("inf"), float("inf"), -float("inf")
l, lMn, lMx = dfs(node.left)
r, rMn, rMx = dfs(node.right)
return min(l, node.val - lMx, r, rMn - node.val), min(lMn, node.val), max(rMx, node.val)
return dfs(root)[0]
Input
root = [1,0,48,null,null,12,49]
Output
1
#5 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0783_MinimumDistanceBetweenBSTNodes
{
private int answer;
private int prev;
public int MinDiffInBST(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 = [4,2,6,1,3]
Output
1