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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def minDiffInBST(self, root: TreeNode) -> int:
9 stack, prev_value, min_diff = [], None, float('inf')
10 current = root
11
12 while stack or current:
13 while current:
14 stack.append(current)
15 current = current.left
16 current = stack.pop()
17 if prev_value is not None:
18 min_diff = min(min_diff, current.val - prev_value)
19 prev_value = current.val
20 current = current.right
21
22 return min_diff
23The Python solution uses a procedural stack-based in-order traversal to simulate recursive behavior. During the traversal, the minimum absolute difference is calculated between successive node values.
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.