Euler Tour O(N)
Intuition\nEuler Sandwich to Precompute the Maximum Tree Levels\n\n# Approach\nEuler Tour is a sandwich list of the root node of a tree surrounding the sub-node
# Intuition\nEuler Sandwich to Precompute the Maximum Tree Levels\n\n# Approach\nEuler Tour is a sandwich list of the root node of a tree surrounding the sub-nodes within that tree.\n\ntour: you first create a list of sandwiching Euler Tour list\nmap_indices: you map the indices of where the starting and ending indices are\nmap_prefix_suffix: you calculate the prefix and suffix maximum levels.\ngive_answer: easily computes the maximum level when the subtree is removed.\n\n# Complexity\n- Time complexity:\nO(N)\n\nCalculating the tour, indices, prefix, and suffix takes O(N). After that, each iteration of query takes O(1), a simple calculation based on indexing pre-computed numbers.\n\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\n# Map (list) node reference, height, other_node_height (if enone, -1)\n\ndef tour(euler_tour, node, level):\n    """\n    This function performs an Euler tour (DFS) on the tree.\n    :param euler_tour: list that stores the tour (node value, level)\n    :param node: current node being visited\n    :param level: level of the current node\n    :return: None\n    """\n    if not node:\n        return\n\n    euler_tour.append((node.val, level))\n    tour(euler_tour, node.left, level + 1)\n    tour(euler_tour, node.right, level + 1)\n    euler_tour.append((node.val, level))\n\ndef map_indices(indices, euler_tour):\n    """\n    This function maps node values to their indices in the Euler tour.\n    :param indices: dictionary that stores node values as keys and a list of indices as values\n    :param euler_tour: list that stores the Euler tour (node value, level)\n    :return: None\n    """\n    for i, item in enumerate(euler_tour):\n        indices[item[0]] = indices.get(item[0], []) + [i]\n\ndef map_prefix_suffix(prefix_max, suffix_max, euler_tour):\n    """\n    This function creates prefix and suffix maximum arrays based on the levels in the Euler tour.\n    :param prefix_max: list that stores the maximum level from the start to each index\n    :param suffix_max: list that stores the maximum level from each index to the end\n    :param euler_tour: list that stores the Euler tour (node value, level)\n    :return: None\n    """\n    max_ind = len(euler_tour) - 1\n    for i, (_, level) in enumerate(euler_tour):\n        prefix_max[i] = max(prefix_max[i - 1], level)\n\n        _, suffix_level = euler_tour[max_ind - i]\n        suffix_max[max_ind - i] = max(suffix_max[max_ind - i + 1], suffix_level)\n\ndef give_answer(queries, indices, prefix_max, suffix_max):\n    """\n    This function calculates the answers for the queries.\n    :param queries: list of queries (node values)\n    :param indices: dictionary that maps node values to their indices in the Euler tour\n    :param prefix_max: list that stores the maximum level from the start to each index\n    :param suffix_max: list that stores the maximum level from each index to the end\n    :return: list of answers for the queries\n    """\n    return_answer = []\n    for query in queries:\n        start, end = indices[query]\n        # this includes possibility of list spillover\n        return_answer += [max(prefix_max[start - 1], suffix_max[end + 1])]\n    return return_answer\n\nclass Solution(object):\n    def treeQueries(self, root, queries):\n        """\n        :type root: Optional[TreeNode]\n        :type queries: List[int]\n        :rtype: List[int]\n        """\n        euler_tour = []\n        indices = {}    \n        \n        tour(euler_tour, root, 0)\n\n        map_indices(indices, euler_tour)\n\n        prefix_max = [0 for i in range(len(euler_tour) + 1)]\n        suffix_max = [0 for i in range(len(euler_tour) + 1)]\n\n        map_prefix_suffix(prefix_max, suffix_max, euler_tour)\n\n        return give_answer(queries, indices, prefix_max, suffix_max)\n\n\n```
['Python']