Height of Binary Tree After Subtree Removal Queries

HardTreestree dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary tree with n nodes whose values are exactly 1 through n, and an array queries. Each query is independent: for queries[i], imagine deleting the subtree rooted at the node with that value (the node and all its descendants), and report the height of the remaining tree. The tree is restored before the next query. Height is measured in **edges** on the longest path from the root down to any remaining node. No query names the root, so the root always remains. Return an array where the i-th element answers queries[i]. Recomputing the height for each query is O(n * m); aim for O(n + m) with precomputation.

Examples

Input: root = [1,2,3,4,5,null,6,7], queries = [2,6,3]
Output: [2,3,3]
Removing 2 leaves the path 1 -> 3 -> 6 (height 2). Removing 6 or 3 keeps 1 -> 2 -> 4 -> 7 (height 3).
Input: root = [1,2], queries = [2]
Output: [0]
Only the root remains, which has height 0.

Constraints

  • 2 <= n <= 10^5
  • Node values are exactly `1` through `n`, each used once
  • 1 <= queries.length <= min(n, 10^4)
  • 1 <= queries[i] <= n
  • queries[i] is never the root value

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More tree dp problems