EasyNeetCode150TreeDepth-First SearchBinary Search TreeBinary Tree
Minimum Absolute Difference in BST
Find minimum absolute difference between any two nodes.
Examples
Input
root = [4,2,6,1,3]
Output
1
Min diff: 4-3=1 or 2-1=1 or 3-2=1.
Constraints
- •
Number of nodes in [2,10^4] - •
0 <= Node.val <= 10^5
Approaches
Inorder, find min diff.
CodeT: O(n log n) sort | S: O(n) storage
Track previous value.
CodeT: O(n) | S: O(h) stack
Same approach.
CodeT: O(n) | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Store All Values | O(n log n) sort | O(n) storage | Inorder, find min diff. |
| Inorder Traversal | O(n) | O(h) stack | Track previous value. |
| Inorder Optimized | O(n) | O(h) | Same approach. |
Store All Values
T: O(n log n) sortS: O(n) storage
Inorder, find min diff.
Inorder Traversal
T: O(n)S: O(h) stack
Track previous value.
Inorder Optimized
T: O(n)S: O(h)
Same approach.
Common Mistakes
Not using BST property
Not handling single node
Off-by-one