How to Solve Height of Binary Tree After Subtree Removal Queries

This problem requires calculating the height of a binary tree after performing multiple independent subtree removals. Using a depth-first traversal, we precompute the maximum depth reachable if each node is removed. Once precomputation is done, each query can be answered in constant time, making the solution optimal for large trees and multiple queries.

Problem Statement

You are given the root of a binary tree with n uniquely valued nodes from 1 to n, and an array queries of size m. For each query, you need to calculate the tree's height after removing the entire subtree rooted at the specified node.

Return an array answer of size m where answer[i] represents the height of the tree after the ith subtree removal query. Each query is independent, and the root node will never be removed.

Examples

Example 1

Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]

Output: [2]

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]

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

• The number of nodes in the tree is n.
• 2 <= n <= 105
• 1 <= Node.val <= n
• All the values in the tree are unique.
• m == queries.length
• 1 <= m <= min(n, 104)
• 1 <= queries[i] <= n
• queries[i] != root.val

Solution Approach

Precompute Depths and Heights

Perform a DFS traversal to compute the depth of each node and the height of the subtree rooted at each node. Store the maximum heights for each level to handle removals efficiently.

Track Maximum Heights Per Level

For each depth level, keep track of the two highest subtree heights. When a node is removed, the new height at that level can be derived from the remaining highest height, avoiding repeated traversal.

Answer Queries in O(1) Time

After precomputing the depth and maximum heights, each query simply looks up the affected level and returns the precomputed new height. This ensures all m queries are answered efficiently without re-traversing the tree.

Complexity Analysis

DFS traversal visits all n nodes once, taking O(n) time and O(n) space for storing depths and heights. Each of the m queries is answered in O(1), resulting in total O(n + m) time and O(n) space.

What Interviewers Usually Probe

• Candidate considers preprocessing depths and heights to avoid repeated computation per query.
• Candidate identifies that tracking two maximum heights per level allows O(1) query resolution.
• Candidate correctly handles edge cases such as removing nodes at maximum depth affecting tree height.

Common Pitfalls or Variants

Common pitfalls

• Recomputing tree height from scratch for each query, causing TLE for large n.
• Failing to account for the second largest height at a depth, returning wrong height when the largest node is removed.
• Incorrectly assuming subtree removal affects parent levels without adjusting maximums properly.

Follow-up variants

• Compute remaining subtree sizes instead of heights after removal queries.
• Answer subtree sum queries after removals using a similar traversal and precomputation.
• Handle dynamic insertion and deletion with height updates using segment tree analogs.

How GhostInterview Helps

• GhostInterview precomputes node heights and tracks level maxima to solve queries instantly.
• It highlights potential pitfalls in depth tracking and subtree removal impact for accurate results.
• It provides a structured approach to translate traversal patterns into constant-time query solutions.

Topic Pages

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

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the primary pattern used in Height of Binary Tree After Subtree Removal Queries?

The main pattern is binary-tree traversal and state tracking to precompute the effect of subtree removals on tree height.

Can each query be answered without traversing the entire tree?

Yes, by precomputing the depth and height for each node and tracking level maxima, each query can be answered in O(1) time.

How do I handle removing the node with the current maximum depth?

Keep track of the two tallest subtree heights per depth level so when the tallest is removed, the second tallest determines the new height.

What is the time complexity for n nodes and m queries?

The total time complexity is O(n + m), with O(n) for DFS precomputation and O(1) per query.

Does this method work if the root node is removed?

No, the problem guarantees the root node is never removed; the solution relies on the root remaining to calculate heights correctly.