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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7var minDiffInBST = function(root) {
8 let stack = [], current = root;
9 let prevValue = -1, minDiff = Infinity;
10
11 while (stack.length > 0 || current !== null) {
12 while (current !== null) {
13 stack.push(current);
14 current = current.left;
15 }
16 current = stack.pop();
17 if (prevValue >= 0) {
18 minDiff = Math.min(minDiff, current.val - prevValue);
19 }
20 prevValue = current.val;
21 current = current.right;
22 }
23
24 return minDiff;
25};The JavaScript solution applies an iterative traversal using arrays as stacks. This approach mirrors C and C++ solutions while leveraging JavaScript's dynamic types and flexible Array methods.
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
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.