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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left =
The 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
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.
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.