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