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.
1#
The C solution implements recursive in-order traversal with helper function inOrder. It retains global variables for previous node value and minimum difference, updating them through recursive traversal.