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

Minimum Distance Between BST Nodes

Real-world version: Closest Pair of Shelf Clearances
Tracked in this browser only
Read Minimum Distance Between BST Nodes on LeetCode(opens in a new tab)

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

A warehouse records the vertical clearance of every storage shelf, in millimetres, in a binary search tree keyed by the clearance: for any shelf in the tree, every clearance in the branch to its left is smaller and every clearance in the branch to its right is larger. No two shelves have the same clearance.

The tree arrives as clearances, a level-order listing. The first entry is the clearance at the top of the tree. After that, the listing gives the left branch then the right branch of each shelf already listed, in the order those shelves appear, writing null wherever a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

Two shelves are easy to mix up when their clearances are close together. Return the smallest difference in clearance between any two different shelves in the tree.

The tree always holds at least two shelves, so such a pair always exists.

Examples

Example 1

Input
clearances = [50, 10, null, null, 11]
Output
1

The tree holds three shelves, of clearance 10, 11 and 50. The pair 10 and 11 sit 1 millimetre apart, and no pair sits closer than that.

Example 2

Input
clearances = [40, 3]
Output
37

Only two shelves are recorded, so the single available pair is 3 and 40 and the answer is their difference.

Example 3

Input
clearances = [9, 7, null, 5, null, 3, null, 1]
Output
2

Every shelf here hangs off the left branch of the one above it, giving clearances 9, 7, 5, 3 and 1. Several pairs sit 2 millimetres apart and none sits closer.

Constraints

  • The number of shelves in the tree is in the range [2, 100].
  • 2 <= clearances.length <= 200
  • 0 <= clearances[i] <= 10^5
  • An entry of clearances that is null marks an empty branch rather than a shelf.
  • clearances[0] is never null, and no clearance appears twice.

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 closest_clearance_gap(clearances: list[int | None]) -> int:
Java
public int closestClearanceGap(Integer[] clearances)

More on the same topics