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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public int MinDiffInBST(TreeNode root) {
13 Stack<TreeNode> stack = new Stack<TreeNode>();
14 TreeNode current = root;
15 int prevValue = -1;
16 int minDiff = int.MaxValue;
17
18 while (stack.Count > 0 || current != null) {
19 while (current != null) {
20 stack.Push(current);
21 current = current.left;
22 }
23 current = stack.Pop();
24 if (prevValue >= 0) {
25 minDiff = Math.Min(minDiff, current.val - prevValue);
26 }
27 prevValue = current.val;
28 current = current.right;
29 }
30 return minDiff;
31 }
32}
33Here in the C# implementation, the System.Collections.Generic.Stack class is utilized to keep track of nodes for in-order traversal. Running minimum difference calculations are performed as the nodes are accessed.
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.