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.
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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 private int minDiff = Integer.MAX_VALUE;
10 private Integer prevValue = null;
11
12 public int minDiffInBST(TreeNode root) {
13 inOrder(root);
14 return minDiff;
15 }
16
17 private void inOrder(TreeNode node) {
18 if (node == null) return;
19 inOrder(node.left);
20 if (prevValue != null) {
21 minDiff = Math.min(minDiff, node.val - prevValue);
22 }
23 prevValue = node.val;
24 inOrder(node.right);
25 }
26}
27The Java solution follows a clear recursive pattern, utilizing class variables to store global state between recursion frames. This mirrors the solution patterns of C and C++, while adopting Java's object-oriented paradigms.