Python. beats 95%. DFS bases solution
Intuition\nThe key is to Group nodes  per level.\nfor instance we have nodes [3, 5, 6 ] on level 3.\nqeustion if we cut node = 3. We need extra piece of informa
# Intuition\nThe key is to Group nodes  per level.\nfor instance we have nodes [3, 5, 6 ] on level 3.\nqeustion if we cut node = 3. We need extra piece of information here to answer what would be tree height after. That info is depth of being cut children.\nSo the sctructure of information stored along node is maximum depth.\nAs result we might have on level such dataset [ [3,10], [5,11], [6,7]]\nHaving said that if we still want to cut node=3, tree height will remain 11. and so on\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nDFS - O(N)\nAnswering Queries O(N)\nSorting - O(NLogN)\n\nSo solution has time complexity O(NlogN)\n\n- Space complexity:\nO(N)\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        # mapping level: List[nodes]\n        nodes_on_level = {}\n        # node 2 level mapping as val:level\n        n2l = {}\n\n        # traverse tree to identify\n        # - level of each node\n        # - group nodes on the same level\n        def dfs(node, lvl):\n            if not node:\n                return lvl-1\n            \n            n2l[node.val]=lvl  # we need to know level of each node for fast lookup\n            max_depth_of_children = max(dfs(node.left, lvl+1), dfs(node.right, lvl+1))            \n            if not lvl in nodes_on_level:\n                nodes_on_level[lvl] = {}\n            nodes_on_level[lvl][node.val]=max_depth_of_children\n            \n            return max_depth_of_children\n        \n        dfs(root,1)\n\n        # sort all this crazieness\n        for lvl in nodes_on_level.keys():\n            nodes_on_level[lvl] = sorted(nodes_on_level[lvl].items(), key = lambda x:x[1]) # sort by depth\n              \n        ret = []\n        # answer queries\n        for q in queries:            \n            on_level = nodes_on_level[n2l[q]]\n            if on_level[-1][0] == q:  # we cut most deepest branch\n                if len(on_level) == 1:\n                    ret.append(n2l[q]-2)\n                else:\n                    ret.append(on_level[-2][1] -1)\n            else:\n                ret.append(on_level[-1][1] -1)\n\n        return ret\n        \n```
['Python3']