Minimum Absolute Difference in BST

Easy#530in-order

You get the root of a binary search tree with at least two nodes. Return the smallest difference between the values of any two nodes. Our tree: 20 with children 9 and 31; 9 has children 4 and 15; 31 has only a left child, 24 — the answer is 4, between 24 and 20.

530 Minimum Absolute Difference in BSTWalkthrough · 1×

Example: the smallest gap between two values of a binary search tree: walk it in order and compare each value with the one before.

nonenonenonenonenonenonenone2093141524in order—call stacktop on the right—
not visited yetwaiting on the call stackcurrent callprev, compared with the nodeits value is behind prevnone: an empty child

prev = none: no value seen yet

01/46
restart · back · play · step
Speed
1function getMinimumDifference(root):
2 prev = none // shared by every call of inorder
3 best = infinity
4 inorder(root)
5 return best
6
7function inorder(node):
8 if node is none:
9 return
10 inorder(node.left)
11 if prev is not none:
12 best = min(best, node.val - prev)
13 prev = node.val
14 inorder(node.right)
state
node
–
prev
–
best
–
click a step to go back

← → step · space play/pause

Why it works

  1. In a binary search tree, in-order visits the values sorted, so prev is always the largest value smaller than the node.
  2. In a sorted list the closest pair is always two neighbours: anything further away is at least as far. So n − 1 comparisons with prev cover every pair that can win.
  3. The neighbour in sorted order is often not the parent: 24 is next to the root 20, two levels up.

Complexity

Time O(n): every node is visited once and compared once. Memory O(h), where h is the height of the tree: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.