Show problems as
Classic problem #230MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Kth Smallest Element in a BST

Real-world version: Kth Lowest Call Number
Tracked in this browser only
Read Kth Smallest Element in a BST on LeetCode(opens in a new tab)

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

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

Python
def kth_lowest_call_number(shelf: list, k: int) -> int:
Java
public int kthLowestCallNumber(Integer[] shelf, int k)

More on the same topics