Upstream of both

Two valves in an orchard's irrigation network need servicing, and the water has to be shut off above both. The numbering stamped on the valves tells you where to stop.

The problem

Water enters the orchard at the head gate and fans out through a tree of valves. Each valve feeds at most two below it and carries a distinct meter number. The crew numbered the network deliberately: from any valve, every number in the branch below-left is smaller than that valve's own, and every number below-right is larger — for the whole branch, not only the two valves directly beneath.

Two valves, first and second, need work. The water must be shut at one valve upstream of both, and the crew wants the lowest such valve, because every block fed from higher up goes dry while the work runs. A valve counts as upstream of itself: if one target sits on the pipe run down to the other, that target is the answer.

Input. meters — the network in level order, top row first, with None where a branch is absent. first, second — two distinct meter numbers, both present.

Output. The meter number of the lowest valve upstream of both.

Example.

meters = [40, 20, 60, 10, 30, 50, 70, None, None, 25, 35]
first = 10, second = 35   ->  20

Both numbers are below 40, so the head gate is upstream of both but not the lowest. At valve 20 they part: 10 runs left, 35 runs right. Valve 20 is the last pipe they share.

A second example, where a target is itself the answer:

meters = [40, 20, 60, 10, 30, 50, 70, None, None, 25, 35]
first = 20, second = 35   ->  20

Valve 35 hangs below valve 20, so closing 20 stops both.

Constraints.

• 2 <= number of valves <= 10^4
• meter numbers are distinct, 1 <= number <= 10^9
• first != second, and both are present in the network
• the ordering rule holds at every valve

Hints

Approach

Brute force

For each valve, walk its branch and check whether both targets appear in it, then keep the deepest one that passes. A membership walk costs O(n) and there are n valves, so this is O(n²) — around 10⁸ valve visits at the top of the range. Recording both paths from the head gate and comparing them drops that to O(n), but it still searches the network as if the numbers meant nothing.

The insight

You never have to search for either valve: the answer is the first valve on the descent whose number lies between the two targets, inclusive, because that is where the searches for them separate.

The precondition is the whole-branch ordering rule. While both targets are smaller than the current number they live in its left branch, so the left valve is upstream of both as well and the current one is not the lowest; the right side mirrors it. The first time the targets straddle the current number — or one equals it — a further step drops a target out of the branch.

Algorithm

1. Let low = min(first, second) and high = max(first, second).
2. Stand at the head gate.
3. If high is below the current number, step to the left valve.
4. If low is above it, step to the right valve.
5. Otherwise low <= current <= high: return the current meter number.

Complexity

Time O(h) where h is the height — one comparison per row, about 14 rows for a balanced network of 10⁴ valves and 10⁴ for one laid as a single chain. Space O(1): the descent carries one pointer, with no recursion and no path lists.

Solution

"""Upstream of both — the lowest shared valve found by one ordered descent."""

from collections import deque


class Valve:
    """A junction: its meter number and the two branches fed from it."""

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

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


def build(meters):
    """Rebuild the network from a level-order list, None marking an absent branch."""
    if not meters or meters[0] is None:
        return None
    head = Valve(meters[0])
    queue = deque([head])
    i = 1
    while queue and i < len(meters):
        valve = queue.popleft()
        if i < len(meters):
            value = meters[i]
            i += 1
            if value is not None:
                valve.left = Valve(value)
                queue.append(valve.left)
        if i < len(meters):
            value = meters[i]
            i += 1
            if value is not None:
                valve.right = Valve(value)
                queue.append(valve.right)
    return head


def solve(meters, first, second):
    # Order the pair once so neither branch test depends on the caller's order.
    low, high = min(first, second), max(first, second)
    valve = build(meters)
    # Invariant: every valve reached is upstream of both targets. While the pair
    # sits strictly on one side, the valve below is upstream of both as well, so
    # this one is not the lowest; the first valve inside [low, high] is.
    while valve is not None:
        if high < valve.meter:
            valve = valve.left
        elif low > valve.meter:
            valve = valve.right
        else:
            return valve.meter
    return None


ORCHARD = [40, 20, 60, 10, 30, 50, 70, None, None, 25, 35]

TESTS = [
    ((ORCHARD, 10, 35), 20),        # the split point, one row below the head gate
    ((ORCHARD, 20, 35), 20),        # a target is upstream of the other
    ((ORCHARD, 25, 70), 40),        # the head gate itself is the answer
    ((ORCHARD, 35, 10), 20),        # same pair, handed over in the other order
    ((ORCHARD, 50, 70), 60),        # both targets down the right branch
    (([8, 3], 3, 8), 8),            # the smallest legal network
    (([10, None, 20, None, 30], 20, 30), 20),   # a chain: no branching at all
    (([10, None, 20, None, 30], 10, 30), 10),   # a chain, answer at the top
]

Pitfalls

• Writing the right-branch test as low >= current. With targets 20 and 35, standing at valve 20, that steps down to 30 and returns 30, which is not upstream of 20. Equality is the stopping case, not a reason to go on.
• Assuming first < second. Called with first = 35, second = 10, code that goes left on current > second walks 40 → 20 → 10 and returns 10, which is not upstream of 35.
• Inspecting the children instead of the valve you stand on. For targets 25 and 70 the answer is the head gate itself, and a loop that only looks one row down reports 20 or 60.

Variants

• The BST invariant — the ordering rule this descent leans on, and what breaks when you read it as a parent-child rule rather than a whole-subtree one.
• Structure and paths — the postorder shape for when the values carry no ordering and one descent decides nothing.