Python3 |  100% T | 85% S | O(N) Time and Space | Explained for Beginner Friendly
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can think of solving offline query. \nNot all nodes will affect the height of tree, 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can think of solving offline query. \nNot all nodes will affect the height of tree, only those node who are in path of maximum height will affect the height of tree\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet\'s say leaf node <code> X</code>  is giving the longest height. Now let\'s say path from root to <code> X</code> is like n1 -> n2 -> n3 -> n4 -> <code> X</code>.\nSo removing only these node will alter your height. \nSo we start from root, check the level of left and right, and whichever is greater, removing that will affect the answer. Whichever is lower, removing that won\'t change our height. \nWe do recursively to all nodes. \n<code> curmx </code> is the current maximum height if we remove the curent node.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nO(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], q : List[int]) -> List[int]:\n        lvl =  defaultdict(int)\n        mx = 0\n        def level(node):\n            nonlocal mx\n            if not node:\n                return 0\n            l = level(node.left)\n            r = level(node.right)\n            lvl[node.val] = max(l,r) +1\n            mx = max(mx, lvl[node.val])\n            return lvl[node.val]\n        level(root)\n        n = len(lvl) + 3\n        ans = [mx-1 for i in range(n+1)]\n        curmx = 0\n        def helper(node, cur):\n            if not node:\n                return \n            nonlocal curmx\n            # print(node.val)\n            l,r = 0,0\n            if node.left:\n                l = lvl[node.left.val] \n            if node.right:\n                r = lvl[node.right.val] \n            if r > l:\n                right = node.right.val\n                curmx = max(curmx, cur + l)\n                ans[right] = curmx\n                helper(node.right, cur + 1)\n            elif l > r:\n                left = node.left.val\n                curmx = max(curmx, cur + r)\n                ans[left] = curmx\n                helper(node.left, cur + 1)\n            else:\n                return\n        helper(root, 0)\n        return [ans[i] for i in q]\n\n            \n```
['Python3']