Watch 10 video solutions for Height of Binary Tree After Subtree Removal Queries, a hard level problem involving Array, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 11,108 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the root of a binary tree with n nodes. Each node is assigned a unique value from 1 to n. You are also given an array queries of size m.
You have to perform m independent queries on the tree where in the ith query you do the following:
queries[i] from the tree. It is guaranteed that queries[i] will not be equal to the value of the root.Return an array answer of size m where answer[i] is the height of the tree after performing the ith query.
Note:
Example 1:
Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4] Output: [2] Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4. The height of the tree is 2 (The path 1 -> 3 -> 2).
Example 2:
Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8] Output: [3,2,3,2] Explanation: We have the following queries: - Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4). - Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1). - Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6). - Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).
Constraints:
n.2 <= n <= 1051 <= Node.val <= nm == queries.length1 <= m <= min(n, 104)1 <= queries[i] <= nqueries[i] != root.valProblem Overview: You are given a binary tree and multiple queries. Each query removes the subtree rooted at a specific node, and you must return the height of the remaining tree after that removal. Since queries are independent and the tree resets after each one, recomputing the height from scratch per query is too slow.
Approach 1: Dynamic Programming with Rerooting (O(n + q) time, O(n) space)
Precompute two values for every node: the height of its own subtree and the maximum height reachable from the rest of the tree when that subtree is removed. The first DFS computes subtreeHeight[node]. A second DFS propagates the best height from ancestors and sibling branches using a rerooting technique. For each child, you compare the height contributed by the parent side and the sibling subtree to determine the maximum remaining height if that child’s subtree disappears. Store the result in an array indexed by node value so each query becomes an O(1) lookup. Total preprocessing runs in O(n) with O(n) memory.
This approach relies heavily on tree traversal patterns from Depth-First Search and the idea of rerooting dynamic programming on a Binary Tree. It avoids repeated recomputation by pushing "outside subtree" heights down the tree.
Approach 2: Recursive Approach with Memoization (O(n + q) time, O(n) space)
A recursive solution can also compute subtree heights and cache them using memoization. First traverse the tree and store the height of each node’s subtree. Then perform another recursive traversal where each call receives the best height available from ancestors. When exploring a child, compute the best alternative path using the parent contribution and the sibling subtree height. Memoization ensures subtree heights are reused instead of recalculated. Each node is processed a constant number of times, leading to O(n) preprocessing and O(1) per query.
The recursion effectively simulates a rerooting DP but keeps the implementation closer to natural recursive tree traversal logic. Many engineers prefer this version because it mirrors how you reason about heights propagating through ancestors and siblings.
Recommended for interviews: The rerooting dynamic programming approach is the expected solution. Interviewers want to see that you recognize recomputing tree height per query is too expensive and that you can precompute subtree heights plus "outside" contributions. Explaining the naive recomputation idea first shows understanding of the problem, while implementing the two-pass DFS demonstrates strong tree DP skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Rerooting | O(n + q) | O(n) | Optimal solution when many queries require subtree removal results |
| Recursive Approach with Memoization | O(n + q) | O(n) | When you prefer a clean recursive tree traversal while still caching subtree heights |