Tree Height After Cutting a Branch

Hard

You are given the root of a binary tree with n nodes whose values are the distinct numbers 1 to n, and an array cuts. Each cuts[i] is a separate question: what would the tree's height be if the node with value cuts[i] were cut off together with its whole subtree? The questions are independent: the tree is restored after each one. The root is never cut. The height of a tree is the number of edges on the longest downward path from the root to any node. Return the answers in the order of the questions.

Example 1

root=tree_node([4, 2, 6, 1, 3, None, 5, None, None, None, 7]), cuts=[3, 6] → [2, 3]

Without the subtree of 3 the longest branch is 4 → 6 → 5, height 2. Without the subtree of 6 the branch 4 → 2 → 3 → 7 remains, height 3. Each cut is applied to the original tree.

Example 2

root=tree_node([1, 2, None, 3]), cuts=[3, 2] → [1, 0]

The tree is the chain 1 → 2 → 3. Cutting 3 leaves height 1; cutting 2 leaves only the root, height 0.

Constraints

2 ≤ n ≤ 10⁵
node values are distinct and lie between 1 and n
1 ≤ len(cuts) ≤ min(n, 10⁴)
1 ≤ cuts[i] ≤ n
cuts[i] is never the root's value

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Array Binary Tree

Similar problems

Tree Columns With Ties Hard Meeting Point on a Route Hard Identical Trees Easy Mirror-Image Tree Easy Tree Height Easy

Input

root=tree_node([4, 2, 6, 1, 3, None, 5, None, None, None, 7]), cuts=[3, 6]

Expected

[2, 3]

Run checks the first 3 tests in your browser. Submit checks all 33 tests on the server, hidden ones included.