simple and fast - DFS + heap
Intuition\n Describe your first thoughts on how to solve this problem. \nEach node has a height and a depth associated with it. Height is the number of levels a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nEach node has a height and a depth associated with it. Height is the number of levels above the node and depth is the number of levels below the node. So the nodes potential contribution to the maximum height of the binary tree is its height + depth (+/- 1 depending on how you track these variables). We will have a max heap for each level of the tree. We will calculate the potential contribution of each nodes height+depth to the max height of the tree and put this value into its levels heap. We put this into the max_heap (depth + height, height, node.val). Finally we have three situations to consider:\n\n1, q is the only node on this level. We return the HEIGHT of any of the nodes one level above our level.\n\n2, we have more than one node in our lvl, but q is on the top of the heap. We simply lookup the next biggest HEIGHT + DEPTH value in the heap.\n\n3, we have more than one node in our lvl and q is not on the top of the heap. We simply add the HEIGHT + DEPTH value from the top of the heap.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N) + q * O(logN)\nO(N) - to precompute the answers\nO(logN) - per query to look up the answer\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) - the combined heaps hold N nodes\n\n\n# Code\n```\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        node_to_lvl = {}\n        lvls = defaultdict(list)\n\n        def dfs(node, height):\n            if not node:\n                return 0\n            height += 1\n            left = dfs(node.left, height) + 1\n            right = dfs(node.right, height) + 1\n            node_to_lvl[node.val] = height\n            heapq.heappush(lvls[height], (-max(left, right) - height + 1, height, node.val))\n            return max(left, right)\n        \n        dfs(root, -1)\n        res = []\n\n        for q in queries:\n            lvl = node_to_lvl[q]\n            if q == root.val:\n                res.append(0)\n            elif len(lvls[lvl]) == 1:\n                res.append(lvls[lvl - 1][0][1])\n            elif lvls[lvl][0][2] == q:\n                temp = heapq.heappop(lvls[lvl])\n                res.append(-lvls[lvl][0][0])\n                heapq.heappush(lvls[lvl], temp)\n            elif lvls[lvl][0][2] != q:\n                res.append(-lvls[lvl][0][0])\n        \n        return res\n            \n\n```
['Depth-First Search', 'Heap (Priority Queue)', 'Python3']