0709EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

Closest Two Readings in the Pressure Index

Tracked in this browser only

Trains the technique from

LeetCode 530Minimum Absolute Difference in BST

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def smallest_reading_gap(tree: list[int | None]) -> int:

Java

public int smallestReadingGap(Integer[] tree)

The intended approach

Time O(m) for an index of m nodes: each entry of the listing is read once and each node is pushed and popped once.Space O(m) for the rebuilt links and the traversal stack.

Rebuild the parent-child links from the level-order listing by keeping a queue of the nodes already created and handing each of them the next two entries as its children. Then traverse the rebuilt tree left subtree first, node, right subtree, driven by an explicit stack rather than recursion so a completely one-sided index cannot overflow. Because of the search-tree property that traversal visits the readings in increasing order, so the answer is the smallest step between two readings visited one after the other, tracked with a single running previous value.

Pythonentry point: smallest_reading_gap

def smallest_reading_gap(tree):
    # O(m) for m nodes: rebuild the links from the level-order listing, then walk
    # the nodes in order with an explicit stack so a chain of 10^4 nodes is safe.
    size = len(tree)
    value = [tree[0]]
    left = [-1]
    right = [-1]
    order = [0]
    head = 0
    pos = 1
    while head < len(order) and pos < size:
        node = order[head]
        head += 1
        for side in (0, 1):
            if pos >= size:
                break
            entry = tree[pos]
            pos += 1
            if entry is None:
                continue
            child = len(value)
            value.append(entry)
            left.append(-1)
            right.append(-1)
            if side == 0:
                left[node] = child
            else:
                right[node] = child
            order.append(child)

    stack = []
    cur = 0
    prev = None
    best = None
    while stack or cur != -1:
        while cur != -1:
            stack.append(cur)
            cur = left[cur]
        cur = stack.pop()
        if prev is not None:
            gap = value[cur] - prev
            if best is None or gap < best:
                best = gap
        prev = value[cur]
        cur = right[cur]
    return best

The obvious version

Collect every reading that appears in the listing and take the smallest absolute difference over all pairs of them. Quadratic in the node count and it never looks at the tree structure at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_smallest_reading_gap(tree):
    vals = [v for v in tree if v is not None]
    best = None
    for i in range(len(vals)):
        for j in range(i + 1, len(vals)):
            gap = abs(vals[i] - vals[j])
            if best is None or gap < best:
                best = gap
    return best

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in