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<stdio.h>
2#include<stdlib.h>
3#include<limits.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11int minDiffInBST(struct TreeNode* root) {
12 struct TreeNode *stack[10000];
13 int stackSize = 0;
14 struct TreeNode *current = root;
15 int prevValue = -1;
16 int minDiff = INT_MAX;
17
18 while (stackSize > 0 || current != NULL) {
19 while (current != NULL) {
20 stack[stackSize++] = current;
21 current = current->left;
22 }
23 current = stack[--stackSize];
24 if (prevValue >= 0) {
25 minDiff = (current->val - prevValue < minDiff) ? current->val - prevValue : minDiff;
26 }
27 prevValue = current->val;
28 current = current->right;
29 }
30 return minDiff;
31}
32The C solution uses an iterative approach with a stack to perform an in-order traversal. The stack mimics the call stack used in recursion, storing nodes to revisit them in the correct order. The minimum difference is updated whenever a valid consecutive pair is found.
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.
1function
JavaScript's recursive implementation mirrors strategies in prior languages, focusing on functional updates to global state to acquire minimum differences during traversal. The recursive function inOrder maintains simplicity and purity of code.