LeetCode Solutions
783. Minimum Distance Between BST Nodes
Time: $O(n)$ Space: $O(\log n) \to O(n)$
class Solution {
public:
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX;
inorder(root, ans);
return ans;
}
private:
int pred = -1;
void inorder(TreeNode* root, int& ans) {
if (root == nullptr)
return;
inorder(root->left, ans);
if (pred >= 0)
ans = min(ans, root->val - pred);
pred = root->val;
inorder(root->right, ans);
}
};
class Solution {
public int minDiffInBST(TreeNode root) {
inorder(root);
return ans;
}
private int ans = Integer.MAX_VALUE;
private Integer pred = null;
private void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
if (pred != null)
ans = Math.min(ans, root.val - pred);
pred = root.val;
inorder(root.right);
}
}