DFS for subtree heights + BFS for level search
Intuition\n Describe your first thoughts on how to solve this problem. \nConsider nodes on the same level.\nIf a node is being removed, the max height after rem
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nConsider nodes on the same level.\nIf a node is being removed, the max height after removal is the depth of the level and the max height of the remaining subtrees.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst generate subtree heights recursively (DFS) and store them in a hashmap (taking advantage of unique values).\nIterate node removal by BFS and keep track of level depth. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n+q)$$ in total, for $$n$$ and $$q$$ being the number of nodes and number of queries, respectively.\n$$O(n)$$ for DFS and BFS.\n$$O(q)$$ for $$q \\times O(1)$$ queries.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ for storing max heights before and after removal.\n\n# Code\n```python3 []\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        heights = {}\n\n        # get subtree\'s heights by dfs\n        def get_height(node):\n            if not node:\n                return -1\n            if node in heights:\n                return heights[node.val]\n            \n            height = 1 + max(get_height(node.left), get_height(node.right))\n            heights[node.val] = height\n            return height\n        get_height(root)\n\n        # bfs approach:\n        # on each level, find two subtrees with the largest heights, h1 >= h2\n        # each node on the same level is being cut.\n        # if node.val = h1, max_height = depth + h2, else depth + h1\n        # h1, h2 = -1, -1 at initialisation since a null child implies a step back to parent\n        max_heights = {root.val: 0}\n        queue = deque([root])\n        depth = 0\n        while queue:\n            k = len(queue)\n            # get first and second max heights\n            h1, h2 = -1, -1\n            for i in range(k):\n                h = heights[queue[i].val]\n                if h > h1:\n                    h1, h2 = h, h1\n                elif h > h2:\n                    h2 = h\n            while k:\n                k -= 1\n                node = queue.popleft()\n                h = heights[node.val]\n                if h == h1:\n                    max_heights[node.val] = h2 + depth\n                else:\n                    max_heights[node.val] = h1 + depth\n                if node.left:\n                    queue.append(node.left)\n                if node.right:\n                    queue.append(node.right)\n            depth += 1\n            \n        return [max_heights[q] for q in queries]\n```
['Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Python3']