Height of Binary Tree After Subtree Removal Queries

Height of Binary Tree After Subtree Removal Queries

What is this problem about?

The Height of Binary Tree After Subtree Removal Queries coding problem asks you to process several independent queries on a binary tree. For each query, you are given a node value. You must calculate the height of the tree if the subtree rooted at that node were completely removed. Crucially, each query is independent, meaning the tree "resets" after each query.

Why is this asked in interviews?

This "Hard" level problem is frequently asked by Microsoft and Google to test a candidate's ability to optimize recursive operations on trees. A naive approach would be to perform a traversal for each query, which results in $O(N imes Q)$ time complexity. Interviewers look for an $O(N + Q)$ solution, which requires preprocessing the tree to understand how the removal of one branch affects the overall height. It evaluates mastery of Depth-First Search interview patterns and the ability to track "alternative paths" in a tree.

Algorithmic pattern used

This problem uses DFS with Precomputation or Level-wise Max Height tracking.

1. Perform a DFS to calculate the depth and height of every node.
2. Store the maximum height and second maximum height for each level of the tree.
3. When a node at level $L$ is removed, the new height of the tree is:
   • If the removed node's branch was the one contributing to the level's max height, the new height depends on the second max height at that level.
   • Otherwise, the maximum height remains unchanged.
4. Alternatively, you can use a "Two-pass DFS" (left-to-right and right-to-left) to precalculate the max height seen excluding the current subtree.

Example explanation

Imagine a tree where the root has a left child of height 5 and a right child of height 3.

• Overall height = 5.
• Query: Remove left child. The tree height becomes the height of the right child (3).
• Query: Remove right child. The tree height remains 5 because the left branch still exists. The preprocessing step allows you to answer these questions in $O(1)$ time by knowing what the "next best" height at the root's children was.

Common mistakes candidates make

• BFS/DFS per Query: Re-traversing the tree for every query, which is far too slow for $10^5$ queries.
• Ignoring Global Root Height: Forgetting that the height is relative to the root, not just the local parent.
• State Management: Failing to correctly store the "alternative" max height for each depth level.

Interview preparation tip

When dealing with "independent removal" queries on trees or graphs, think about how to precalculate the "max excluding X." This often involves tracking the top two maximums or using prefix/suffix-style processing on siblings.