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.
1import java.util.Stack;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10class Solution {
11 public int minDiffInBST(TreeNode root) {
12 Stack<TreeNode> stack = new Stack<>();
13 TreeNode current = root;
14 int prevValue = -1;
15 int minDiff = Integer.MAX_VALUE;
16
17 while (!stack.isEmpty() || current != null) {
18 while (current != null) {
19 stack.push(current);
20 current = current.left;
21 }
22 current = stack.pop();
23 if (prevValue >= 0) {
24 minDiff = Math.min(minDiff, current.val - prevValue);
25 }
26 prevValue = current.val;
27 current = current.right;
28 }
29
30 return minDiff;
31 }
32}
33In this Java solution, we employ an explicit stack to carry out the in-order traversal. The stack behaves akin to explicit recursion, ensuring the nodes are visited in increasing order. The minimum difference is computed on-the-fly during traversal.
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#include<iostream>
#include<limits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
int minDiff = numeric_limits<int>::max();
int prevValue = -1;
public:
void inOrder(TreeNode* node) {
if (node == nullptr) return;
inOrder(node->left);
if (prevValue >= 0) {
minDiff = min(minDiff, node->val - prevValue);
}
prevValue = node->val;
inOrder(node->right);
}
int minDiffInBST(TreeNode* root) {
prevValue = -1;
minDiff = numeric_limits<int>::max();
inOrder(root);
return minDiff;
}
};
In C++, recursive in-order traversal adjusts a class member as it traverses and computes minimal differences. The method offers a sleek encapsulation of pointer handling, benefiting from C++ class structures.