Show problems as
Classic problem #2458HardArrayTreeDepth-First SearchBreadth-First SearchBinary Tree

Height of Binary Tree After Subtree Removal Queries

Real-world version: The Rig's Depth After Cutting a Section
Tracked in this browser only
Read Height of Binary Tree After Subtree Removal Queries on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tree_queries(rig: list, cuts: list[int]) -> list[int]:
Java
public int[] treeQueries(Integer[] rig, int[] cuts)

More on the same topics