The espalier weave

A pear tree trained flat against a wall branches at most twice at every bud, one shoot tied left and one tied right. The gardener wants the longest run that crosses over at every step.

The problem

An espalier is grown against a south wall. Each bud carries at most two shoots: one trained to the left, one to the right. A weave is a walk down the tree that changes side at every step — left, right, left, ... or right, left, right, ... — and its length is the number of shoots walked, so a bud with no shoots is a weave of length 0.

The weave may start at any bud, not only at the base, and it stops as soon as the side it needs next is missing. Report the number of shoots in the longest weave anywhere on the tree.

Input. espalier — the buds in level order, with None where a shoot is missing. A missing shoot is never given shoots of its own.

Output. An integer, the shoots in the longest weave.

Example.

espalier = [1, 2, 3, 4, None, None, 5, None, 6, None, None, 8, None, None, 10]

        1
      /   \
     2     3
    /       \
   4         5
    \
     6
    /
   8
    \
     10

->  4

The weave 2 -> 4 -> 6 -> 8 -> 10 goes left, right, left, right: four shoots. Starting at the base is worse — bud 1 leaves to the left onto bud 2, and bud 2's only shoot is also to the left, so that weave dies after one step.

A second example, where every shoot leans the same way:

espalier = [1, 2, None, 3, None, 4]   ->  1

Buds 1, 2, 3 and 4 hang in one left-leaning chain. Every weave takes its first shoot and then asks for a right-hand shoot that is not there.

Constraints.

• 1 <= number of buds <= 5000
• Bud labels are distinct integers and do not affect the answer
• The listing contains labels and None only; None is never given children

Hints

Approach

Brute force

Start a walk at every bud, in both directions, and follow it to the end. That is 2n walks, each up to the height of the tree, so O(n·h) steps — about 12 million for a 5000-bud tree trained as one long weave. Every walk re-treads shoots the previous one already measured.

The insight

The longest weave leaving a bud to the left is one shoot plus the longest weave leaving its left shoot to the right.

Two numbers per bud settle everything: out_left and out_right. Each is defined purely from its shoots' numbers, so nothing is circular and one pass in reverse level order fills them all — level order lists parents before shoots, so reading it backwards reaches every shoot before the bud that carries it. The answer is the largest number in the whole table, because a weave may start anywhere.

Algorithm

1. Grow the buds from the level-order listing, keeping them in level order.
2. Walk that list backwards, so both shoots of a bud are already settled.
3. out_left is 0 if there is no left shoot, else 1 plus that shoot's out_right. Mirror it for out_right.
4. Track the running maximum over both numbers of every bud.

Complexity

Time O(n) — one pass to grow the tree, one to fill the numbers, no bud touched more than twice. Space O(n) for the buds themselves; the table adds only two integers per bud.

Solution

"""The espalier weave — two numbers per bud, one for each side it can be left by."""

from collections import deque


class Bud:
    __slots__ = ("label", "left", "right", "out_left", "out_right")

    def __init__(self, label):
        self.label = label
        self.left = None
        self.right = None
        self.out_left = 0
        self.out_right = 0


def train(level_order):
    """Grow the espalier from its level-order listing; None marks a missing shoot.

    Returns the buds in level order, so a parent always precedes its shoots.
    """
    if not level_order or level_order[0] is None:
        return []
    root = Bud(level_order[0])
    order = [root]
    queue = deque([root])
    i = 1
    while queue and i < len(level_order):
        bud = queue.popleft()
        if i < len(level_order):
            label = level_order[i]
            i += 1
            if label is not None:
                bud.left = Bud(label)
                queue.append(bud.left)
                order.append(bud.left)
        if i < len(level_order):
            label = level_order[i]
            i += 1
            if label is not None:
                bud.right = Bud(label)
                queue.append(bud.right)
                order.append(bud.right)
    return order


def solve(espalier):
    buds = train(espalier)
    if not buds:
        return 0
    longest = 0
    # out_left is the weave that leaves this bud to the left, so it continues
    # with the weave that leaves the left shoot to the RIGHT. Walking level
    # order backwards settles every shoot before the bud that carries it.
    for bud in reversed(buds):
        bud.out_left = 1 + bud.left.out_right if bud.left else 0
        bud.out_right = 1 + bud.right.out_left if bud.right else 0
        longest = max(longest, bud.out_left, bud.out_right)
    return longest

TESTS = [
    (([1, 2, 3, 4, None, None, 5, None, 6, None, None, 8, None, None, 10],), 4),
    (([7, None, 8, 9, None, None, 10],), 3),
    (([1, 2, None, 3, None, 4],), 1),   # one long left-leaning chain
    (([5],), 0),                        # a lone bud walks no shoots
    (([1, 2, 3, 4, 5, 6, 7],), 2),      # a full tree: base, left shoot, its right
]

Pitfalls

• Counting buds instead of shoots. The weave 2 -> 4 -> 6 -> 8 -> 10 visits five buds and walks four shoots; returning 5 is the classic off-by-one here.
• Returning the base's number. In the first example that gives 1, not 4, because the longest weave never touches the base.
• Reading the same side on the shoot. out_left must consult the left shoot's out_right. Consulting its out_left measures the longest all-left chain instead, which is a different quantity entirely.
• Recursing down a 5000-bud chain. A plain recursive walk overflows the interpreter's stack; the reverse level-order pass never recurses.

Variants

• Paying by the tray — the same "answer that ends here" idea over a straight line of crates instead of a branching tree.
• The pier ticker — a state that also carries the last step taken, but the set of steps left over comes with it.