Segment Tree | O(nlogn)
Approach\nDo a dfs traversal to append each depth (from root to leaf) to compute a list depth. \n\npre and post determine the range of element in depth list so 
# Approach\nDo a dfs traversal to append each depth (from root to leaf) to compute a list `depth`. \n\n`pre` and `post` determine the range of element in `depth` list so that all values inside this range are from path rooted at this node. \n\nFor each queries, we want to find out the max depth without choosing element from this range, so we use segment tree to query max depth before pre[node] and max depth after pre node, as well as the depth of the parent of this node.\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(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\n\nclass SegmentTree:\n    def __init__(self, n, fn): # fn is transformation function\n        self.n = n\n        self.fn = fn\n        self.tree = [0] * (2 * self.n)\n    \n    def update(self, idx, val):\n        idx += self.n\n        \n        self.tree[idx] = val\n        while idx > 1:\n            idx >>= 1\n            self.tree[idx] = self.fn(self.tree[2 * idx], self.tree[2 * idx + 1])\n        \n    def query(self, lo, hi):\n        lo += self.n\n        hi += self.n + 1\n        res = 0\n        \n        while lo < hi:\n            if lo & 1 == 1:\n                res = self.fn(res, self.tree[lo])\n                lo += 1\n            if hi & 1 == 1:\n                hi -= 1\n                res = self.fn(res, self.tree[hi])\n            lo >>= 1\n            hi >>= 1\n        \n        return res \n    \nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        pre = defaultdict(int)\n        post = defaultdict(int)\n        height = defaultdict(int)\n        depth = []\n        \n        def dfs(node, curr):\n            if not node: return\n            \n            height[node.val] = curr\n            pre[node.val] = len(depth)\n            dfs(node.left, curr + 1)\n            dfs(node.right, curr + 1)\n            \n            if len(depth) == pre[node.val]: # node is leaf\n                post[node.val] = pre[node.val]\n                depth.append(curr)\n            else:\n                post[node.val] = len(depth) - 1\n            \n        dfs(root, 0)\n        seg = SegmentTree(len(depth), max)\n        for i in range(len(depth)):\n            seg.update(i, depth[i])\n        \n        res = []\n        for q in queries:\n            lo, hi = pre[q], post[q]\n            \n            d = 0\n            if lo == 0 and hi == len(depth) - 1:\n                res.append(height[q] - 1)\n            elif lo == 0:\n                res.append(max(seg.query(hi + 1, len(depth) - 1), height[q] - 1))\n            elif hi == len(depth) - 1:\n                res.append(max(seg.query(0, lo - 1), height[q] - 1))\n            else:\n                res.append(max(seg.query(0, lo - 1), seg.query(hi + 1, len(depth) - 1), height[q] - 1))\n            \n        return res        \n        \n        \n        \n        \n        \n        \n    \n    \n    \n\n```
['Python3']