0473MediumTreeBinary Search TreeBinary Tree

Threading a Weight Onto the Parcel Rack

Tracked in this browser only

Trains the technique from

LeetCode 701Insert into a Binary Search 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 depot hangs its parcel weight cards on a rack shaped as a search tree. Every card has a lighter peg and a heavier peg below it. All weights hanging anywhere below a card's lighter peg are strictly smaller than that card's weight, and all weights hanging anywhere below its heavier peg are strictly larger. All weights on the rack are distinct.

A new card of weight weight arrives, and it is guaranteed that no card on the rack already carries that weight. Thread it in the way the depot always does: start at the top card and, at each card, move to its lighter peg when the new weight is smaller and to its heavier peg when the new weight is larger. The first time that peg is empty, hang the new card there. No existing card may be moved, re-hung or re-weighed.

How a rack is written down. Both tree and the value you return use the same flat listing. Put the top card into a waiting line on its own. Then repeatedly take the front of the line: write its weight at the end of the listing, and add to the back of the line whatever hangs on its lighter peg and then whatever hangs on its heavier peg, adding the marker null for an empty peg. When null reaches the front of the line, write null to the listing and add nothing. Stop when the line runs dry, then delete any null entries sitting after the last weight. An empty rack is written as the empty list [].

Return the listing of the rack after the new card has been threaded in.

Examples

Example 1

Input: tree = [50, 30, 70], weight = 60
Output: [50, 30, 70, null, null, 60]

60 is heavier than 50 and lighter than 70, so it ends up on the lighter peg of the card holding 70. The two empty pegs under 30 keep their `null` markers because a weight is written after them.

Example 2

Input: tree = [], weight = 40
Output: [40]

The rack is bare, so the new card becomes the top card and the listing holds nothing else.

Example 3

Input: tree = [10, null, 20, null, 30], weight = 25
Output: [10, null, 20, null, 30, 25]

Each card on this rack hangs from a heavier peg. The walk passes 10 and 20, then stops at the lighter peg of the card holding 30.

Constraints

The number of cards on the rack is in the range [0, 10^4].
-10^8 <= card weight <= 10^8
All card weights are distinct.
-10^8 <= weight <= 10^8
weight is guaranteed not to be on the rack already.

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 thread_in_weight(tree: list, weight: int) -> list:

Java

public List<Integer> threadInWeight(List<Integer> tree, int weight)

The intended approach

Time O(n) overall for n cards, the walk to the empty peg being O(h) for height hSpace O(n) for the rebuilt cards plus the returned listing

Read the listing back into linked cards with a queue, mirroring the way the listing is laid out: each card taken off the queue claims the next two entries as its two pegs. Then follow the depot's rule with a plain loop from the top card, turning lighter or heavier on each comparison, and attach the new card at the first empty peg the loop meets. Finally lay the rack back out with the same queue rule and trim the trailing markers. The loop is used rather than recursion so a rack that is one long chain of ten thousand cards is fine.

Pythonentry point: thread_in_weight

from collections import deque


class Slot:
    __slots__ = ("weight", "lighter", "heavier")

    def __init__(self, weight):
        self.weight = weight
        self.lighter = None
        self.heavier = None


def _grow(listing):
    if not listing or listing[0] is None:
        return None
    root = Slot(listing[0])
    line = deque([root])
    at = 1
    while line and at < len(listing):
        node = line.popleft()
        if at < len(listing):
            entry = listing[at]
            at += 1
            if entry is not None:
                node.lighter = Slot(entry)
                line.append(node.lighter)
        if at < len(listing):
            entry = listing[at]
            at += 1
            if entry is not None:
                node.heavier = Slot(entry)
                line.append(node.heavier)
    return root


def _spell(root):
    out = []
    line = deque([root])
    while line:
        node = line.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.weight)
        line.append(node.lighter)
        line.append(node.heavier)
    while out and out[-1] is None:
        out.pop()
    return out


def thread_in_weight(tree, weight):
    # Walk down once, hang the card on the empty peg the walk stops at.
    # time O(n) overall, of which the walk itself is O(h) for height h
    # space O(n) for the rebuilt cards and the returned listing
    root = _grow(tree)
    fresh = Slot(weight)
    if root is None:
        return _spell(fresh)
    node = root
    while True:
        if weight < node.weight:
            if node.lighter is None:
                node.lighter = fresh
                return _spell(root)
            node = node.lighter
        else:
            if node.heavier is None:
                node.heavier = fresh
                return _spell(root)
            node = node.heavier

The obvious version

Rebuild the rack into parallel arrays, then try hanging the new card on every empty peg in turn. After each attempt, walk the whole rack in weight order and check the walk is strictly increasing; the one placement that passes is the answer. No use is made of the search property to decide where to go.

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 bf_thread_in_weight(tree, weight):
    if not tree or tree[0] is None:
        return [weight]
    val = [tree[0]]
    lo = [-1]
    hi = [-1]
    order = [0]
    at = 1
    head = 0
    while head < len(order) and at < len(tree):
        node = order[head]
        head += 1
        for side in (0, 1):
            if at >= len(tree):
                break
            entry = tree[at]
            at += 1
            if entry is None:
                continue
            val.append(entry)
            lo.append(-1)
            hi.append(-1)
            kid = len(val) - 1
            if side == 0:
                lo[node] = kid
            else:
                hi[node] = kid
            order.append(kid)

    def bf_inorder_ok():
        seen = []
        stack = []
        node = 0
        while stack or node != -1:
            while node != -1:
                stack.append(node)
                node = lo[node]
            node = stack.pop()
            seen.append(val[node])
            node = hi[node]
        for i in range(1, len(seen)):
            if seen[i - 1] >= seen[i]:
                return False
        return True

    def bf_layout():
        out = []
        line = [0]
        at2 = 0
        while at2 < len(line):
            node = line[at2]
            at2 += 1
            if node == -1:
                out.append(None)
                continue
            out.append(val[node])
            line.append(lo[node])
            line.append(hi[node])
        while out and out[-1] is None:
            out.pop()
        return out

    total = len(val)
    for node in range(total):
        for side in (0, 1):
            if (lo[node] if side == 0 else hi[node]) != -1:
                continue
            val.append(weight)
            lo.append(-1)
            hi.append(-1)
            fresh = len(val) - 1
            if side == 0:
                lo[node] = fresh
            else:
                hi[node] = fresh
            if bf_inorder_ok():
                return bf_layout()
            if side == 0:
                lo[node] = -1
            else:
                hi[node] = -1
            val.pop()
            lo.pop()
            hi.pop()
    return []

How this problem was checked

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