Level + Depth
I initially solved this problem as O(m * h), but I got TLE when the trie is a vine (so the complexity is O(m * n)). The level-based approach below is O(n + m) f
I initially solved this problem as O(m * h), but I got TLE when the trie is a vine (so the complexity is O(m * n)). The level-based approach below is O(n + m) for any tree shape.\n\nFor each node, we store its `level` and `depth` of its subtree.\n\nAlso, for each level, we store largest (`d1`) and second largest (`d2`) depth from all nodes on that level.\n\nNow, when we process a query, we can figure out the level and depth of the node.\n\nThe result is the level plus a) the largets depth of that level, or b) second largest if the queried node depth is the largest.\n\n**C++**\n```cpp\nint level[100001] = {}, depth[100001] = {};\nint d1[100001] = {}, d2[100001] = {};\nint traverse(TreeNode* n, int l = 0) {\n    if (n == nullptr)\n        return 0;\n    level[n->val] = l;\n    depth[n->val] = 1 + max(traverse(n->left, l + 1), traverse(n->right, l + 1));   \n    if (d1[l] < depth[n->val]) {\n        d2[l] = d1[l];\n        d1[l] = depth[n->val];\n    } \n    else if (d2[l] < depth[n->val])\n        d2[l] = depth[n->val];\n    return depth[n->val];\n};\nvector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n    traverse(root, 0);\n    transform(begin(queries), end(queries), begin(queries), [&](int q){\n        int l = level[q];\n        return l + (d1[l] == depth[q] ? d2[l] : d1[l]) - 1;\n    });\n    return queries;\n}\n```
['C']