DFS | One pass solution | Very Detail Explanation ✅
\n# Approach\nUsing DFS to travel for each level of tree. When travel, remember to store these important information of each level:\n- Number of node with same 
\n# Approach\nUsing DFS to travel for each level of tree. When travel, remember to store these important information of each level:\n- Number of node with same level\n- Max value among these node\n- Second max value among these node.\n\nAnother thing to save is a hash map, linking a node val to level and depth of subnode. \n```\nlevel_map = dict() => value: (level, depth_of_subnode)\n```\n\nNow, for each of queries. These are some step to do:\n- Find the level using `level_map`\n- If this level has number of node is 1 return `level - 1`\n- If the depth of current query is equal `max_` of its level return `level + second_max`. Else return `level + max_`\n# Complexity\n- Time complexity: $$O(n)$$\n    Travel each node: $$O(n)$$\n    Travel each query: $$O(m) < O(n)$$\n\n- Space complexity: $$O(n)$$\n    Store depth_map: $$O(n)$$ (n is the worst case for 1 side tree)\n    Store level_map: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(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        depth_map = defaultdict(lambda :(-1, -1, 0))\n        level_map = {}\n        def travel(root, level):\n            if not root:\n                return 0\n            depth = max(travel(root.left, level + 1), travel(root.right, level + 1))\n            level_map[root.val] = (level, depth)\n            max_, second_max, size = depth_map[level]\n            if depth >= max_:\n                depth_map[level] = (depth, max_, size + 1)\n            elif depth > second_max:\n                depth_map[level] = (max_, depth, size + 1)\n            else:\n                depth_map[level] = (max_, second_max, size + 1)\n            return depth + 1\n        travel(root, 0)\n        result = []\n        for q in queries:\n            level, depth = level_map[q]\n            max_, second_max, size = depth_map[level]\n            if size == 1:\n                result.append(level - 1)\n                continue\n            if depth == max_:\n                result.append(level + second_max)\n            else:\n                result.append(level + max_) \n        return result\n```
['Hash Table', 'Depth-First Search', 'Python3']