<p>You are given the <code>root</code> of a <strong>binary tree</strong> with <code>n</code> nodes. Each node is assigned a unique value from <code>1</code> to <code>n</code>. You are also given an array <code>queries</code> of size <code>m</code>.</p>

<p>You have to perform <code>m</code> <strong>independent</strong> queries on the tree where in the <code>i<sup>th</sup></code> query you do the following:</p>

<ul>
	<li><strong>Remove</strong> the subtree rooted at the node with the value <code>queries[i]</code> from the tree. It is <strong>guaranteed</strong> that <code>queries[i]</code> will <strong>not</strong> be equal to the value of the root.</li>
</ul>

<p>Return <em>an array </em><code>answer</code><em> of size </em><code>m</code><em> where </em><code>answer[i]</code><em> is the height of the tree after performing the </em><code>i<sup>th</sup></code><em> query</em>.</p>

<p><strong>Note</strong>:</p>

<ul>
	<li>The queries are independent, so the tree returns to its <strong>initial</strong> state after each query.</li>
	<li>The height of a tree is the <strong>number of edges in the longest simple path</strong> from the root to some node in the tree.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-1.png" style="width: 495px; height: 281px;" />
<pre>
<strong>Input:</strong> root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
<strong>Output:</strong> [2]
<strong>Explanation:</strong> 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 -&gt; 3 -&gt; 2).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/07/binaryytreeedrawio-2.png" style="width: 301px; height: 284px;" />
<pre>
<strong>Input:</strong> root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
<strong>Output:</strong> [3,2,3,2]
<strong>Explanation:</strong> We have the following queries:
- Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -&gt; 8 -&gt; 2 -&gt; 4).
- Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -&gt; 8 -&gt; 1).
- Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -&gt; 8 -&gt; 2 -&gt; 6).
- Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -&gt; 9 -&gt; 3).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>All the values in the tree are <strong>unique</strong>.</li>
	<li><code>m == queries.length</code></li>
	<li><code>1 &lt;= m &lt;= min(n, 10<sup>4</sup>)</code></li>
	<li><code>1 &lt;= queries[i] &lt;= n</code></li>
	<li><code>queries[i] != root.val</code></li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
        """
        1. First objective to get the height and depth of each node.
        2. If a node is removed and if it happens to be the node that contributed to the longest height of the tree,
           then the height of the tree now becomes => current depth + node in this level with highest depth

        Procedure.
        1. Traverse the tree and record the depth and height of each node
        2. Group the nodes of the same depth recording their heights and values

        3. If the len of the number of nodes in a group is equal to 1, then we know we lost the longest
            at that level
            If the selected value has the longest height in the branch, the new height would include the current 
            depth and the next heighest branch
            If the selected value was not the longest height in the branch, then the new height is the depth value 
            and the height of the highest node in that depth 

        """
        
        nodeHeights = {}
        nodeDepths = {}
        answer = []
        def recordHeightAndDepth(node, depth,nodeHeights, nodeDepths):

            if not node: return -1

            nodeDepths[node.val] = depth
            height = 1 + max(recordHeightAndDepth(node.left, depth + 1, nodeHeights, nodeDepths), recordHeightAndDepth(node.right, depth + 1, nodeHeights, nodeDepths))
            nodeHeights[node.val] = height
            return height

        recordHeightAndDepth(root, 0, nodeHeights, nodeDepths)
        #now we create the depth Groups
        depthGroups = collections.defaultdict(list)

        for key, depth in nodeDepths.items():
            height = nodeHeights[key]
            depthGroups[depth].append(height)
            depthGroups[depth].sort(reverse = True)

            if len(depthGroups[depth]) > 2: depthGroups[depth].pop()

        for q in queries:
            curr_node_depth = nodeDepths[q]
            curr_node_height = nodeHeights[q]

            if len(depthGroups[curr_node_depth]) == 1:
                answer.append(curr_node_depth - 1)

            elif depthGroups[curr_node_depth][0] > curr_node_height:
                answer.append(curr_node_depth + depthGroups[curr_node_depth][0])

            else:
                answer.append(curr_node_depth + depthGroups[curr_node_depth][1])

        return answer
56016