Sponsored
Sponsored
In this approach, we will perform an in-order traversal of the BST using an explicit stack to store the node values in a sorted manner. As we traverse the tree, we will calculate the minimum difference between consecutive values.
Time Complexity: O(N), where N is the number of nodes. Each node is visited exactly once.
Space Complexity: O(H), where H is the height of the tree, representing the maximum size of the stack.
1#include<iostream>
2#include<stack>
3#include<limits>
4using namespace std;
5
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode() : val(0), left(nullptr), right(nullptr) {}
11 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15int minDiffInBST(TreeNode* root) {
16 stack<TreeNode*> stk;
17 TreeNode* current = root;
18 int prevValue = -1;
19 int minDiff = numeric_limits<int>::max();
20
21 while (!stk.empty() || current != nullptr) {
22 while (current != nullptr) {
23 stk.push(current);
24 current = current->left;
25 }
26 current = stk.top();
27 stk.pop();
28 if (prevValue >= 0) {
29 minDiff = min(minDiff, current->val - prevValue);
30 }
31 prevValue = current->val;
32 current = current->right;
33 }
34 return minDiff;
35}
36The C++ solution implements an iterative in-order traversal using a standard library stack to find the minimum difference. The approach mirrors the C solution but utilizes C++ specific features such as the standard stack and numeric limits.
This approach relies on a recursive in-order traversal of the BST to compute the minimum absolute difference. We maintain a global variable to track the smallest difference encountered during traversal.
Time Complexity: O(N)
Space Complexity: O(H), due to recursive call stack.
1
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int? prevValue = null;
private int minDiff = int.MaxValue;
public int MinDiffInBST(TreeNode root) {
InOrder(root);
return minDiff;
}
private void InOrder(TreeNode node) {
if (node == null) return;
InOrder(node.left);
if (prevValue != null) {
minDiff = Math.Min(minDiff, node.val - prevValue.Value);
}
prevValue = node.val;
InOrder(node.right);
}
}
C# adoption introduces nullable types for tracking node values. In this way, each recursion elegantly handles missing values without need for excessive condition checks, exemplifying C#'s language features.