0166MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Kth Lowest Call Number

Tracked in this browser only

Trains the technique from

LeetCode 230Kth Smallest Element in a 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 lending library files its catalogue as a lookup tree. Each filed entry carries one call number, and an entry may hang up to two entries beneath it: one on its lower peg and one on its upper peg.

The filing rule holds everywhere in the tree. For any entry, every call number sitting anywhere in the branch below its lower peg is smaller than that entry's own number, and every call number anywhere in the branch below its upper peg is larger. Because the comparisons are strict, a call number never repeats.

The harness hands you plain JSON, so the tree arrives as the array shelf, read peg row by peg row starting from the topmost entry. Position 0 holds the topmost entry's call number. The remaining positions arrive in pairs, and each pair gives the lower-peg entry and then the upper-peg entry of one already-listed entry, taken in that same row order. An empty peg is written null and contributes no pair of its own, and the array may stop early once no further entries remain.

Report the call number that holds rank k once the whole catalogue is placed in increasing order, where rank 1 belongs to the smallest number on file. At least k entries are always filed, so exactly one number answers.

Examples

Example 1

Input: shelf = [50, 30, 70, 20, 40, 60, 80], k = 3
Output: 40

Sorting the seven call numbers gives 20, 30, 40, 50, 60, 70, 80, and the third of those is 40.

Example 2

Input: shelf = [18, 9, 27, null, 12], k = 1
Output: 9

Entry 9 hangs on the lower peg of 18 and its own lower peg is empty, so nothing in the catalogue is filed before it.

Example 3

Input: shelf = [4], k = 1
Output: 4

A single filed entry is both the smallest and the only candidate.

Constraints

The catalogue holds n entries, and n is in the range [1, 10^4].
1 <= k <= n
0 <= shelf[i] <= 10^4 for every position that is not `null`.
Call numbers are distinct and `shelf` describes a correctly filed lookup tree.

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 kth_lowest_call_number(shelf: list, k: int) -> int:

Java

public int kthLowestCallNumber(Integer[] shelf, int k)

The intended approach

Time O(n)Space O(n)

The filing rule means that walking lower peg, then entry, then upper peg visits call numbers in increasing order, so the k-th entry that walk reaches is the answer. Rebuild the entries from the peg-row array, then run that walk with an explicit stack, counting visits and returning as soon as the count hits k. No sort is needed, and the walk stops early, though the rebuild still has to read the whole array before the walk can start.

Pythonentry point: kth_lowest_call_number

def kth_lowest_call_number(shelf, k):
    # Time: O(n) -- one sweep rebuilds the entries, then an in-order walk that
    #               halts the moment the k-th entry is reached.
    # Space: O(n) -- the rebuilt entries plus the explicit traversal stack.
    if not shelf or shelf[0] is None:
        return -1
    nodes = [[shelf[0], None, None]]
    at = 0
    i = 1
    while at < len(nodes) and i < len(shelf):
        cur = nodes[at]
        at += 1
        for slot in (1, 2):
            if i >= len(shelf):
                break
            v = shelf[i]
            i += 1
            if v is not None:
                cur[slot] = [v, None, None]
                nodes.append(cur[slot])
    stack = []
    cur = nodes[0]
    seen = 0
    while stack or cur is not None:
        while cur is not None:
            stack.append(cur)
            cur = cur[1]
        cur = stack.pop()
        seen += 1
        if seen == k:
            return cur[0]
        cur = cur[2]
    return -1

The obvious version

Collect every call number, then for each one count how many other numbers fall below it by scanning the whole collection again. The number with exactly k - 1 below it is the answer.

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_kth_lowest_call_number(shelf, k):
    if not shelf or shelf[0] is None:
        return -1
    nodes = [[shelf[0], None, None]]
    at = 0
    i = 1
    while at < len(nodes) and i < len(shelf):
        cur = nodes[at]
        at += 1
        for slot in (1, 2):
            if i >= len(shelf):
                break
            v = shelf[i]
            i += 1
            if v is not None:
                cur[slot] = [v, None, None]
                nodes.append(cur[slot])
    values = [node[0] for node in nodes]
    for v in values:
        below = 0
        for w in values:
            if w < v:
                below += 1
        if below == k - 1:
            return v
    return -1

How this problem was checked

Reference solution executed against 15 test cases — 15 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