Solution: Height of Binary Tree After Subtree Removal Queries

Statement

We are given the root of a binary tree with $n$ nodes and an array, queries, of size $m$. Each query represents the root of a subtree that should be removed from the tree. The task here is to determine the height of the binary tree after each query, i.e., once a subtree is removed. We'll store the updated heights against each query in an array and return it.

Note: A tree’s height is the number of edges in the longest path from the root to any leaf node in the tree.

A few points to be considered:

• All the values in the tree are unique.

• It is guaranteed that queries[i] will not be equal to the value of the root.

• The queries are independent, so the tree returns to its initial state after each query.

Constraints:

• $2 \leq$ $n$ $\leq 500$

• $1 \leq$ Node.data $\leq$ $n$

• $m$ == queries.length

• $1 \leq$ $m$ $\leq min($$n$, $400)$

• $1 \leq$ queries[i] $\leq$ $n$

• queries[i] $\neq$ root.data

Solution

To solve this problem efficiently, it’s crucial to understand the fundamental structure of a tree. When we trace a path from the root to a leaf node, each node on this path has two important measures.

• The first is the distance from the root to the node, referred to as the node’s depth.

• The second is the distance from the node to the farthest leaf node, known as the node’s height.