[Tutorial From The Problem Contributor] DFS 1 time converts to a Range Removal Problem
Topic :  DFS\n\nAs the contributor to this problem, I\'d like to share the intended solution that I developed while working through it during my Google intervie
**Topic** :  DFS\n\nAs the **contributor** to this problem, I\'d like to share the intended solution that I developed while working through it during my **Google** interview.\n\n**Contributor**:\n![image](https://assets.leetcode.com/users/images/d1e9695f-ffaa-49ce-be95-528bbaf0db1c_1729907298.017787.png)\n\n___\n\n## Solution\nFirst, let\'s consider how to determine the height of a tree **without any removal operations**.\nLet `mp2[i]` represent the height of a single node `i`, defined as the number of nodes along the path from the root node to node `i`. The height of the tree is simply the maximum value in the array `mp2`.\n\nWhen we remove a subtree, we eliminate some values from `mp2`. Consequently, **the height of the remaining tree** will be the **maximum** value among the remaining values in `mp2`.  Is there a way to remove those values from `mp2` elegantly?\n\nYes, we can assign each node a unique `ID` to represent its value.  **The `ID` will be assigned according to the preorder traversal order of the tree.** Now, `mp2[i]` denotes the number of nodes along the path from the root node to the node with ID `i`.\n\nLet\'s also calculate the size of each subtree. If we remove a subtree rooted at `u`, this means we remove all IDs from `ID[u]` to `ID[u] + subtreeSize[u] - 1` consecutively. By removing a consecutive range from `mp2`, we can easily compute the maximum value among the remaining elements.\n\nWe have an array `left[i]` that represents the maximum value of `mp2` from index `0` to `i`, and an array `right[i]` that represents the maximum value of `mp2` from index `i` to the end. If we remove a range `[l : r]` from `mp2`, the answer will simply be `max(left[l - 1], right[r + 1])`.\n\n\n<br/><br/>\n\n```c++\nclass Solution {\npublic:\n    unordered_map<int, int> mp1, mp2, sz;\n    int id = 0;\n    vector<int> treeQueries(TreeNode* root, vector<int>& q) {\n        vector<int> ans;\n        dfs(root, 0);\n        \n        vector<int> left(id), right(id);\n        for(int i = 0; i < left.size(); i++) {\n            left[i] = mp2[i];\n            if(i) left[i] = max(left[i - 1], left[i]);\n        }\n        \n        for(int i = right.size() - 1; i >= 0; i--) {\n            right[i] = mp2[i];\n            if(i + 1 < right.size()) right[i] = max(right[i], right[i + 1]);\n        }\n        \n        for(int i = 0; i < q.size(); i++) {\n            int nodeid = mp1[q[i]];\n            int l = nodeid, r = l + sz[nodeid] - 1;\n            int h = 0;\n            if(l > 0) h = max(h, left[l - 1]);\n            if(r + 1 < right.size()) h = max(h, right[r + 1]);\n            ans.push_back(h);\n        }\n        return ans;\n    }\n    \n    int dfs(TreeNode* root, int h) { //return the size of the subtree\n        if(root == NULL) {\n            return 0;\n        }\n        mp1[root -> val] = id;\n        mp2[id] = h;\n        id++;\n        int lz = dfs(root -> left, h + 1);\n        int rz = dfs(root -> right, h + 1);\n        sz[mp1[root -> val]] = (1 + lz + rz);\n        return 1 + lz + rz;\n    }\n};\n```\n\n```java\nclass Solution {\n    Map<Integer, Integer> mp1 = new HashMap<>(), mp2 = new HashMap<>(), sz = new HashMap<>();\n    int id = 0;\n    public int[] treeQueries(TreeNode root, int[] q) {\n        int[] ans = new int[q.length];\n        dfs(root, 0);\n        \n        int[] left = new int[id];\n        int[] right = new int[id];\n        for (int i = 0; i < id; i++) {\n            left[i] = mp2.get(i);\n            if (i > 0) left[i] = Math.max(left[i - 1], left[i]);\n        }\n        \n        for (int i = id - 1; i >= 0; i--) {\n            right[i] = mp2.get(i);\n            if (i + 1 < id) right[i] = Math.max(right[i], right[i + 1]);\n        }\n        \n        for (int i = 0; i < q.length; i++) {\n            int nodeId = mp1.get(q[i]);\n            int l = nodeId, r = l + sz.get(nodeId) - 1;\n            int h = 0;\n            if (l > 0) h = Math.max(h, left[l - 1]);\n            if (r + 1 < id) h = Math.max(h, right[r + 1]);\n            ans[i] = h;\n        }\n        return ans;\n    }\n    \n    private int dfs(TreeNode root, int h) {\n        if (root == null) {\n            return 0;\n        }\n        mp1.put(root.val, id);\n        mp2.put(id, h);\n        id++;\n        int lz = dfs(root.left, h + 1);\n        int rz = dfs(root.right, h + 1);\n        sz.put(mp1.get(root.val), 1 + lz + rz);\n        return 1 + lz + rz;\n    }\n}\n```\n\n```python\nclass Solution:\n    def __init__(self):\n        self.mp1 = {}\n        self.mp2 = {}\n        self.sz = {}\n        self.id = 0\n    \n    def treeQueries(self, root: Optional[TreeNode], q: List[int]) -> List[int]:\n        self.dfs(root, 0)\n        left = [0] * self.id\n        right = [0] * self.id\n        \n        for i in range(self.id):\n            left[i] = self.mp2[i]\n            if i > 0:\n                left[i] = max(left[i - 1], left[i])\n        \n        for i in range(self.id - 1, -1, -1):\n            right[i] = self.mp2[i]\n            if i + 1 < self.id:\n                right[i] = max(right[i], right[i + 1])\n        \n        ans = []\n        for node in q:\n            nodeid = self.mp1[node]\n            l, r = nodeid, nodeid + self.sz[nodeid] - 1\n            h = 0\n            if l > 0:\n                h = max(h, left[l - 1])\n            if r + 1 < self.id:\n                h = max(h, right[r + 1])\n            ans.append(h)\n        \n        return ans\n    \n    def dfs(self, root: Optional[TreeNode], h: int) -> int:\n        if not root:\n            return 0\n        self.mp1[root.val] = self.id\n        self.mp2[self.id] = h\n        self.id += 1\n        lz = self.dfs(root.left, h + 1)\n        rz = self.dfs(root.right, h + 1)\n        self.sz[self.mp1[root.val]] = 1 + lz + rz\n        return 1 + lz + rz\n        \n```\n\n\n**Complexity**:\n* Time Complexity : `O(n)`.\n* Space Complexity : `O(n)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['C', 'Python', 'Java']