Sponsored
Sponsored
An inorder traversal of a BST yields nodes in non-decreasing order. By performing an inorder traversal, we can collect the values of the nodes in a sorted manner and then iterate through these values to find the minimum difference between successive nodes.
Time Complexity: O(N), where N is the number of nodes in the tree since we visit each node exactly once.
Space Complexity: O(H) due to the recursion stack, where H is the height of the tree.
1#include <iostream>
2#include <vector>
3#include <climits>
4using namespace std;
5
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11};
12
13void inorder(TreeNode* root, int& prev, int& minDiff) {
14 if (root == NULL) return;
15 inorder(root->left, prev, minDiff);
16 if (prev != -1) {
17 minDiff = min(minDiff, root->val - prev);
18 }
19 prev = root->val;
20 inorder(root->right, prev, minDiff);
21}
22
23int minDiffInBST(TreeNode* root) {
24 int minDiff = INT_MAX;
25 int prev = -1;
26 inorder(root, prev, minDiff);
27 return minDiff;
28}Similar to the C solution, we perform an inorder traversal, keeping track of the minimum difference. This approach leverages C++'s min function for cleaner code.
The Morris Traversal is an inorder tree traversal technique that uses constant space by reusing the tree structure. It involves temporarily rearranging the tree to allow traversal without explicit stack use.
Time Complexity: O(N) where each edge is traversed at most twice, once down and once up.
Space Complexity: O(1) because it does not use stack or recursion.
1 public int MinDiffInBST(TreeNode root) {
int minDiff = int.MaxValue;
int? prev = null;
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
if (prev.HasValue) {
minDiff = Math.Min(minDiff, curr.val - prev.Value);
}
prev = curr.val;
curr = curr.right;
} else {
TreeNode pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
pred.right = curr;
curr = curr.left;
} else {
pred.right = null;
if (prev.HasValue) {
minDiff = Math.Min(minDiff, curr.val - prev.Value);
}
prev = curr.val;
curr = curr.right;
}
}
}
return minDiff;
}
}C# solution mirrors Morris Traversal logic using nullable integer checks for robust absent-value handling. It threads and unthreads as needed for traversal without extra space.