0391MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Widest Trellis Tier

Tracked in this browser only

Trains the technique from

LeetCode 662Maximum Width of Binary Tree

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 vine trellis is built in tiers. One plant sits at the top, and every plant may send a shoot down-left and a shoot down-right into the tier below it, so tier 0 has one slot, tier 1 has two slots, tier 2 has four, and so on. Slots with no shoot in them are simply empty.

The trellis arrives as trellis, a tier-by-tier listing. trellis[0] is the top plant's tag. The rest of the list is consumed two entries at a time, taking plants in the order they were listed: the next two entries are that plant's down-left and down-right tags, and null means that shoot is absent, so it contributes no entries of its own. Trailing nulls are omitted.

The width of a tier is the number of slots covered when you go from its leftmost filled slot to its rightmost filled slot inclusive; empty slots that lie between those two ends still count, because the framework holds them whether a shoot arrived or not.

Return the largest width over all tiers.

Examples

Example 1

Input: trellis = [3, 5, 8, 2, null, null, 7]
Output: 4

Tier 2 has plant 2 in its first slot and plant 7 in its fourth slot, with the two middle slots empty, so it covers four slots.

Example 2

Input: trellis = [1, 2, 3, 4, null, null, 5, 6, null, null, 7]
Output: 8

Tier 3 has plant 6 in its first slot and plant 7 in its eighth slot, so it covers eight slots.

Example 3

Input: trellis = [1, 2, null, 4]
Output: 1

Each tier holds a single plant, so no tier covers more than one slot.

Example 4

Input: trellis = [7]
Output: 1

The trellis is a single plant on tier 0.

Constraints

The number of plants on the trellis is in the range [1, 3000].
-100 <= plant tag <= 100

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 width_of_binary_tree(trellis: list) -> int:

Java

public int widthOfBinaryTree(Integer[] trellis)

The intended approach

Time O(n)Space O(n)

Rebuild the trellis, then sweep it one whole tier at a time while carrying each plant's slot number. A plant in slot `s` sends its shoots to slots `2s` and `2s + 1` of the tier below, and because the tier is swept left to right the first and last entries hold the extreme slots, so the width is their difference plus one. Slot numbers are rebased against the tier's leftmost slot before the children are produced, which keeps them small on a trellis 3000 tiers deep.

Pythonentry point: width_of_binary_tree

def _decode(trellis):
    if not trellis or trellis[0] is None:
        return None
    nodes = [[trellis[0], None, None]]
    order = [0]
    i = 1
    qi = 0
    while qi < len(order) and i < len(trellis):
        node = nodes[order[qi]]
        qi += 1
        for slot in (1, 2):
            if i >= len(trellis):
                break
            label = trellis[i]
            i += 1
            if label is not None:
                nodes.append([label, None, None])
                node[slot] = len(nodes) - 1
                order.append(len(nodes) - 1)
    return nodes


def width_of_binary_tree(trellis):
    # Time O(n) -- every plant is placed on exactly one tier.
    # Space O(n) for the rebuilt trellis plus the widest tier held at once.
    nodes = _decode(trellis)
    if nodes is None:
        return 0
    best = 0
    tier = [(0, 0)]
    while tier:
        left_edge = tier[0][1]
        span = tier[-1][1] - left_edge + 1
        if span > best:
            best = span
        nxt = []
        for idx, slot in tier:
            node = nodes[idx]
            rebased = slot - left_edge
            if node[1] is not None:
                nxt.append((node[1], 2 * rebased))
            if node[2] is not None:
                nxt.append((node[2], 2 * rebased + 1))
        tier = nxt
    return best

The obvious version

Walk the trellis depth-first with an explicit stack, recording the slot number of every plant against its tier in two dictionaries of extremes, then take the largest difference. Slot numbers are never rebased, so they grow without bound on a deep trellis.

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 _decode2(trellis):
    if not trellis or trellis[0] is None:
        return None
    nodes = [[trellis[0], None, None]]
    order = [0]
    i = 1
    qi = 0
    while qi < len(order) and i < len(trellis):
        node = nodes[order[qi]]
        qi += 1
        for slot in (1, 2):
            if i >= len(trellis):
                break
            label = trellis[i]
            i += 1
            if label is not None:
                nodes.append([label, None, None])
                node[slot] = len(nodes) - 1
                order.append(len(nodes) - 1)
    return nodes


def bf_width_of_binary_tree(trellis):
    nodes = _decode2(trellis)
    if nodes is None:
        return 0
    lo = {}
    hi = {}
    stack = [(0, 0, 0)]
    while stack:
        idx, tier, slot = stack.pop()
        node = nodes[idx]
        if tier not in lo or slot < lo[tier]:
            lo[tier] = slot
        if tier not in hi or slot > hi[tier]:
            hi[tier] = slot
        if node[1] is not None:
            stack.append((node[1], tier + 1, 2 * slot))
        if node[2] is not None:
            stack.append((node[2], tier + 1, 2 * slot + 1))
    return max(hi[t] - lo[t] + 1 for t in lo)

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
4 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