Smallest Gap Between Labels

EasyTrees

Problem

A binary search tree with at least two nodes holds distinct integer labels.

Return the smallest absolute difference between the values of any two different nodes.

Example 1

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

Sorted values are 1, 2, 3, 4, 6; neighbours 1–2, 2–3 and 3–4 differ by 1.

Example 2

Input:
root = [1, 0, 48, null, null, 12, 49]
Output:
1

Constraints

  • 2 ≤ number of nodes ≤ 10^4
  • -10^5 ≤ node.val ≤ 10^5
  • All values are distinct.

Hint

Show the first hint

If the values were sorted, which pairs would you need to compare?

Walkthrough

How to approach it

01Clarify before coding

  • Any two nodes, not only parent and child? Yes, any pair.
  • Values distinct? Yes, so the answer is at least 1.
  • At least two nodes? Yes, an answer always exists.

02Brute force

Collect all values and compare every pair.

Cost: O(n²) time: 5·10^7 comparisons for 10^4 nodes.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.