Show problems as
Classic problem #530EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

Minimum Absolute Difference in BST

Real-world version: Closest Two Readings in the Pressure Index
Tracked in this browser only
Read Minimum Absolute Difference in BST on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A monitoring rig indexes its pressure readings in a binary search tree: every reading in a node's left subtree is smaller than that node's reading, and every reading in its right subtree is larger. All readings in the index are different.

The index arrives as tree, a level-order listing of the nodes. tree[0] is the root's reading. The remaining entries are consumed in order, two at a time, giving the left child and then the right child of each node already listed, taken in the order the nodes were listed. A null entry means there is no child there, and an absent node contributes no entries of its own. The listing stops once every remaining child would be absent.

Return the smallest absolute difference between the readings of two different nodes.

Walk the tree itself rather than sorting the entries of the listing.

Examples

Example 1

Input
tree = [10, 5, 20, null, 8, 12, null]
Output
2

The index holds the readings 5, 8, 10, 12 and 20. The pair 8 and 10 differ by 2, and no pair of readings in the index is closer than that.

Example 2

Input
tree = [50, 25, 75, 12, 37, 62, 87]
Output
12

The readings are 12, 25, 37, 50, 62, 75 and 87. The pair 25 and 37 differ by 12, which is the closest any two of them come.

Example 3

Input
tree = [100000, 0]
Output
100000

The index has only the two readings 0 and 100000, so the answer is the difference between them.

Constraints

  • 2 <= tree.length <= 2 * 10^4
  • 0 <= tree[i] <= 10^5
  • The index holds between 2 and 10^4 nodes.
  • Every entry of tree is either a reading or null, and tree[0] is a reading.
  • The listing describes a binary search tree with all readings different.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_reading_gap(tree: list[int | None]) -> int:
Java
public int smallestReadingGap(Integer[] tree)

More on the same topics