Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3] Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49] Output: 1
Constraints:
[2, 104].0 <= Node.val <= 105Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
The key insight for Minimum Absolute Difference in BST is the ordered nature of a Binary Search Tree. When a BST is traversed using inorder traversal, the node values appear in sorted order. This property allows us to compare only adjacent values in the traversal sequence to find the minimum absolute difference.
Instead of storing the entire sorted list, an efficient approach is to perform a Depth-First Search (DFS) inorder traversal while keeping track of the previous visited node. For each current node, compute the difference with the previous value and update the minimum difference accordingly.
This method works because the smallest difference in a sorted sequence must occur between neighboring elements. The traversal touches each node exactly once, giving a time complexity of O(n). The space complexity is O(h), where h is the tree height due to the recursion or stack used during traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Inorder DFS Traversal with Previous Node Tracking | O(n) | O(h) |
NeetCodeIO
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;
int prevValue = -1;
int minDiff = int.MaxValue;
while (stack.Count > 0 || current != null) {
while (current != null) {
stack.Push(current);
current = current.left;
}
current = stack.Pop();
if (prevValue >= 0) {
minDiff = Math.Min(minDiff, current.val - prevValue);
}
prevValue = current.val;
current = current.right;
}
return minDiff;
}
}
Here 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#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In a Binary Search Tree, inorder traversal visits nodes in ascending order. This guarantees that the smallest absolute difference will always appear between two consecutive elements in the traversal sequence.
Yes, BST traversal problems are common in technical interviews, including FAANG-style interviews. This question tests understanding of BST properties, inorder traversal, and how to optimize comparisons during tree traversal.
The optimal approach is to perform an inorder traversal of the BST. Since inorder traversal produces sorted values, you only need to compare each node with the previously visited node to compute the minimum difference efficiently.
The BST itself provides the structure needed for the optimal solution. Using recursion or a stack for DFS traversal while tracking the previous value is sufficient, without requiring additional data structures like arrays.
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.