Minimum Absolute Difference in BST Easy 0 attempts
LeetCode ↗

Minimum Absolute Difference in BST

Easy TreeBinary TreeDFS LeetCode

You're handed the root of a binary search tree (BST). Look at every possible pair of distinct nodes and compute the absolute difference between their values — return the smallest difference found across all such pairs.

Since an inorder walk of a BST produces values in sorted order, the smallest gap always occurs between two values that are neighbors in that ordering. Still, your solution needs to hold for the tree as a whole, not just one neighboring pair.

Input Format
Implement getMinimumDifference(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [4,2,6,1,3]
Output
1

Example 2

Input
root = [10,5,20]
Output
5
Constraints
  • 2 <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^5
Test Cases (2)
Case 1
Args: [[4,2,6,1,3]] Expected: 1
Case 2
Args: [[10,5,20]] Expected: 5
Topics
TreeBinary TreeDFS

Iterative Inorder

The closest pair in a sorted sequence must be adjacent. Track the preceding inorder value and the smallest gap.

javascript
function getMinimumDifference(root) {
  const stack=[];let current=root,previous=-Infinity,best=Infinity;
  while(current||stack.length) {
    while(current){stack.push(current);current=current.left;}
    current=stack.pop();best=Math.min(best,current.val-previous);previous=current.val;current=current.right;
  }
  return best;
}

Time: O(n) | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript