Minimum Absolute Difference in BST
The key idea
An inorder traversal of a BST visits node values in sorted order. The minimum absolute difference between any two nodes must therefore come from two values that are adjacent in that sorted sequence, so you only need to track the previous visited value and compare it to the current one.
Problem
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.
A BST is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. You may assume the tree has at least two nodes.
Constraints
- The number of nodes in the tree is in the range
[2, 10^4]. 0 <= Node.val <= 10^5
Examples
Input: root = [4,2,6,1,3]
Output: 1
Input: root = [1,0,48,null,null,12,49]
Output: 1
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY