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.
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.