1065HardArrayTreeDepth-First SearchBreadth-First SearchBinary Tree

The Rig's Depth After Cutting a Section

Tracked in this browser only

Trains the technique from

LeetCode 2458Height of Binary Tree After Subtree Removal Queries

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 cargo rig is given as the flat list rig. It hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty. Every joint carries a different label, and the labels are the whole numbers from 1 up to however many joints there are.

A flat list is read level by level: its first entry is the top joint's label, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own.

The rig's depth is how many slots the longest run from the top joint downwards passes through, so a rig of one joint has depth 0.

Each entry of cuts asks a separate question, and the rig is never actually cut: were the joint with that label, and everything hanging below it, taken away, what would the rig's depth be? No question names the top joint's label.

Return the answers in the order the questions are asked.

Examples

Example 1

Input: rig = [1, 2, 3, 4, 5], cuts = [2]
Output: [1]

The rig hangs two slots deep, through the joint labelled 2 down to 4 or 5. Cutting the section at 2 leaves only the top joint and the joint labelled 3, one slot deep.

Example 2

Input: rig = [1, 2, 3, 4, 5], cuts = [4]
Output: [2]

The joint labelled 4 hangs bare at the bottom, and its neighbour 5 hangs just as deep, so cutting it leaves the depth unchanged.

Example 3

Input: rig = [1, 2, 3], cuts = [2, 3]
Output: [1, 1]

Either joint below the top may be cut, and each time the other one is left hanging one slot down.

Constraints

2 <= rig.length <= 300000
The rig holds between 2 and 10^5 joints.
1 <= cuts.length <= 10^4
1 <= cuts[i] <= 100000
The first entry of the list is not null.
No entry of cuts is the top joint's label.

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 tree_queries(rig: list, cuts: list[int]) -> list[int]:

Java

public int[] treeQueries(Integer[] rig, int[] cuts)

The intended approach

Time O(n + q) for n joints and q questions.Space O(n) for the three facts per joint.

Answering each question by rebuilding the rig would cost the rig times the questions. Instead work out, for every joint, the depth the rig would have without it, all in a few passes, and then read the answers off. Three facts per joint do it. How far down the joint sits, which comes from a pass from the top. How far the rig hangs below the joint, which comes from a pass from the bottom. And the deepest the rig reaches without ever passing through the joint, which is what a question asks for. That third fact passes down from a joint to its two slots. For a joint's first slot, the deepest reach avoiding it is either the deepest reach already avoiding the joint itself, or a run that turns aside into the joint's second slot, which goes as far as the joint's own depth plus one plus how far the rig hangs below that second slot. When there is no second slot, turning aside stops at the joint, so that run reaches only the joint's own depth. The second slot is handled the same way with the roles swapped. Starting the top joint's own value at nothing, since a rig cut at the top would be empty, and walking the joints from the top downwards fills every joint in one pass. Each question is then a lookup by label.

Pythonentry point: tree_queries

def tree_queries(rig, cuts):

    n = len(rig)
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if rig[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if rig[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt

    depth = {0: 0}
    for pos in order:
        for child in (left.get(pos), right.get(pos)):
            if child is not None:
                depth[child] = depth[pos] + 1
    height = {}
    for pos in reversed(order):
        tall = 0
        for child in (left.get(pos), right.get(pos)):
            if child is not None and height[child] + 1 > tall:
                tall = height[child] + 1
        height[pos] = tall
    best = {0: 0}
    answer = {}
    for pos in order:
        lo = left.get(pos)
        ro = right.get(pos)
        here = best[pos]
        if lo is not None:
            other = depth[pos] + 1 + height[ro] if ro is not None else depth[pos]
            best[lo] = here if here > other else other
            answer[rig[lo]] = best[lo]
        if ro is not None:
            other = depth[pos] + 1 + height[lo] if lo is not None else depth[pos]
            best[ro] = here if here > other else other
            answer[rig[ro]] = best[ro]
    out = []
    for label in cuts:
        out.append(answer[label])
    return out

The obvious version

Answer each question outright: walk the rig from the top measuring how deep it reaches, refusing to enter the joint named by the question, and report that depth. Costs the rig per question rather than three passes in total.

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_tree_queries(rig, cuts):

    n = len(rig)
    left = {}
    right = {}
    order = [0]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            if at < n:
                if rig[at] is not None:
                    left[owner] = at
                    nxt.append(at)
                at += 1
            if at < n:
                if rig[at] is not None:
                    right[owner] = at
                    nxt.append(at)
                at += 1
        order.extend(nxt)
        level = nxt

    spot = {}
    for pos in order:
        spot[rig[pos]] = pos
    def deepest(pos, banned):
        if pos == banned:
            return -1
        tall = 0
        for child in (left.get(pos), right.get(pos)):
            if child is None:
                continue
            below = deepest(child, banned)
            if below >= 0 and below + 1 > tall:
                tall = below + 1
        return tall
    out = []
    for label in cuts:
        out.append(deepest(0, spot[label]))
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 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