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.
1class
In Python, recursive strategy is broken into inner function inOrder to isolate logic from class. This utilizes in-memory numerical comparisons to ensure minimum difference tracking remains accurate and swift.