Kth wheel to ripen

A cheese cellar files every wheel in a sorted index, keyed by the day it comes out. The driver does not want the whole schedule — only the third date on it.

The problem

Wheels of hard cheese age on the racks of a cellar, each filed in a binary index keyed by its ripening day — a day number counted from the start of the season. The index obeys the ordering rule at every node, not only at the root: every day in a node's left subtree is smaller than that node's day, every day in its right subtree is larger. No two wheels share a day.

The van books slots in order of readiness, so the cellarmaster asks for one date at a time: given the index and an integer k, return the ripening day of the k-th wheel to be ready. The index arrives in compact level-order form — the root, then each level left to right, with None for a missing child. A gap lists no children of its own, and trailing gaps are trimmed.

Input. cellar_index — the index in compact level-order. k — an integer, 1 meaning the earliest wheel.

Output. The ripening day of the k-th wheel to be ready.

Example.

cellar_index = [12, 6, 19, 3, 9, None, 24], k = 3   ->  9

The children of 6 are 3 and 9, and 19 has only a right child, 24. Read left-node-right and the days come out 3, 6, 9, 12, 19, 24 — the third is 9.

A second example, where the list order and the day order disagree completely:

cellar_index = [30, 21, None, 14, None, 8], k = 1   ->  8
cellar_index = [30, 21, None, 14, None, 8], k = 4   ->  30

This index is a chain leaning entirely left: 30, then 21, then 14, then 8. The earliest wheel is the deepest node, so the first entry of the list answers k = 4, not k = 1.

Constraints.

• 1 <= number of wheels <= 10^4
• 1 <= k <= number of wheels
• 1 <= ripening day <= 10^6, all distinct
• the ordering rule holds at every node, and the index may be a chain, so its height can reach 10^4

Hints

Approach

Brute force

Collect all n days with any walk, sort them, read position k - 1. For 10⁴ wheels that is 10⁴ visits plus roughly 130,000 comparisons to re-derive an order the index already encodes, and k = 1 costs as much as k = n.

The insight

An inorder walk — left subtree, node, right subtree — emits the days in increasing order, so the k-th day it emits is the answer and the walk can stop right there.

The ordering rule is the precondition, and it holds at every node rather than only the root. By induction on subtree size, left-node-right therefore emits a whole subtree in increasing order. The emissions come out sorted, so the k-th is the k-th smallest and nothing later can change it — the walk stops at k.

Algorithm

1. Rebuild the index, queueing only real wheels so a gap never claims child slots.
2. Start with an empty stack and node at the root.
3. Push node and keep walking left, pushing as you go, until there is no left child.
4. Pop. That node holds the next smallest day; decrement k.
5. If k is 0, return its day. Otherwise move node to its right child and go back to step 3.

Complexity

Time O(h + k), where h is the height — the first descent pushes the left spine, and every node is pushed and popped at most once, so the cost is that descent plus k pops, never worse than O(n). Space O(h) for the stack: about 14 entries for a balanced index of 10⁴ wheels, 10⁴ for the chain above.

Solution

"""Kth wheel to ripen — inorder walk of the cellar index with an explicit stack."""

from collections import deque


class Wheel:
    """One node of the index: a ripening day and two child slots."""

    __slots__ = ("day", "left", "right")

    def __init__(self, day):
        self.day = day
        self.left = None
        self.right = None


def build(level_order):
    """Rebuild the index from its compact level-order form."""
    if not level_order or level_order[0] is None:
        return None
    root = Wheel(level_order[0])
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        # invariant: only real wheels are queued, so a gap never claims child slots
        node = queue.popleft()
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.left = Wheel(value)
                queue.append(node.left)
        if i < len(level_order):
            value = level_order[i]
            i += 1
            if value is not None:
                node.right = Wheel(value)
                queue.append(node.right)
    return root


def solve(cellar_index, k):
    node = build(cellar_index)
    stack = []
    while stack or node:
        while node:
            # invariant: the stack holds ancestors whose day is still uncounted,
            # smallest on top, because every one of them was reached going left
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1                    # a pop is the next day in increasing order
        if k == 0:
            return node.day
        node = node.right         # everything left of this node is already counted
    return None

TESTS = [
    (([12, 6, 19, 3, 9, None, 24], 3), 9),
    (([30, 21, None, 14, None, 8], 1), 8),
    (([30, 21, None, 14, None, 8], 4), 30),
    (([12, 6, 19, 3, 9, None, 24], 1), 3),
    (([12, 6, 19, 3, 9, None, 24], 6), 24),
    (([7], 1), 7),
    (([5, 3, 8, None, 4], 2), 4),
]

Pitfalls

• Counting on the push instead of the pop. Decrementing k as nodes go onto the stack counts them in descent order, not day order: the first example pushes 12, 6 and 3, so k = 3 returns 3 when the answer is 9.
• Recursing over a chain. Recursive inorder is fine on a balanced index, but the constraints allow a 10⁴-node chain like the second example scaled up, and Python's default recursion limit is 1000 — that raises RecursionError.
• Letting a gap claim child slots while rebuilding. A None lists no children, so queueing it shifts every later entry to the wrong parent: on [30, 21, None, 14, None, 8] the 8 hangs off a placeholder and drops out of the index, and k = 1 answers 14.

Variants

• Traversal families — where the three walk orders come from, and why moving one line turns preorder into inorder.
• The BST invariant — the ordering rule this problem leans on, stated over subtrees rather than parent and child.