Beats 99.79% | 3 Code
\n# Solution - 1 (TLE)\ncpp []\nclass Solution {\nprivate:\n    int getDepth(TreeNode * & root,int & nodeForRemove){\n        if(nodeForRemove==root->val) retur
![image.png](https://assets.leetcode.com/users/images/73210da5-3637-41ee-b6be-47e9caf6d058_1729961087.736724.png)\n# Solution - 1 (TLE)\n```cpp []\nclass Solution {\nprivate:\n    int getDepth(TreeNode * & root,int & nodeForRemove){\n        if(nodeForRemove==root->val) return 0;\n        int depth=0;\n        queue<pair<TreeNode*,int>> q;\n        q.push({root,0});\n        while(!q.empty()){\n            TreeNode * node = q.front().first;\n            int currDepth = q.front().second;\n            q.pop();\n\n            depth = max(depth,currDepth);\n\n            if(node->left && node->left->val != nodeForRemove){\n                q.push({node->left,currDepth+1});\n            } \n            if(node->right && node->right->val != nodeForRemove){\n                q.push({node->right,currDepth+1});\n            } \n        }\n        return depth;\n    }\npublic:\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        vector<int> res;\n        for(int & q : queries){\n            res.push_back(getDepth(root,q));\n        }\n        return res;\n    }\n};\n```\n# Solution - 2 (Runtime 1671ms)\n```C++ []\nclass Solution {\nprivate:\n    vector<unordered_map<int,int>> levelOf;\n    unordered_map<int,int> depthOf;\n\n    int getDepth(TreeNode * root,int depth){\n        if(!root) return 0;\n        \n        // store maximum depth in maxDepth\n        int maxDepth = depth;\n\n        // store depth value wise \n        depthOf[root->val] = depth;\n\n        // increase size\n        if(levelOf.size() < depth+1){\n            levelOf.push_back(unordered_map<int,int>());\n        }\n\n        maxDepth = max(maxDepth,getDepth(root->left,depth+1));\n        maxDepth = max(maxDepth,getDepth(root->right,depth+1));\n\n        // store maximum depth\n        levelOf[depth][root->val] = maxDepth;\n\n        return maxDepth;\n    }\npublic:\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        // clear old data\n        levelOf.clear();\n        depthOf = unordered_map<int,int>();\n\n        // perform dfs\n        getDepth(root,0);\n\n        // store depth in res\n        vector<int> res;\n        int depth,maxDepth;\n\n        for(int q : queries){\n            depth = depthOf[q];\n            maxDepth = max(0,depth-1);\n            // check all the nodes on that level \n            for(const auto & [node,nodeMaxDepth] : levelOf[depth]){\n                if(node == q) continue;\n                if(maxDepth == levelOf.size()-1) break;\n                maxDepth = max(maxDepth,nodeMaxDepth);\n            }\n\n            res.push_back(maxDepth);\n        }\n        return res;\n    }\n};\n```\n# Solution - 3 (Runtime - 8 ms)\n```C++ []\nclass Solution {\nprivate:\n    int depthAfterRemoveOf[100001],maxDepth=0;\n\n    void dfsFromLeft(TreeNode * root,int currDepth){\n        if(!root) return ;\n        \n        depthAfterRemoveOf[root->val] = maxDepth;\n\n        maxDepth = max(maxDepth,currDepth);\n\n        dfsFromLeft(root->left,currDepth+1);\n        dfsFromLeft(root->right,currDepth+1);\n    }\n    void dfsFromRight(TreeNode * root,int currDepth){\n        if(!root) return ;\n        \n        depthAfterRemoveOf[root->val] = max(depthAfterRemoveOf[root->val],maxDepth);\n\n        maxDepth = max(maxDepth,currDepth);\n\n        dfsFromRight(root->right,currDepth+1);\n        dfsFromRight(root->left,currDepth+1);\n    }\npublic:\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        dfsFromLeft(root,0);\n        maxDepth = 0;\n        dfsFromRight(root,0);\n        \n        // store depth in res\n        vector<int> res;\n\n        for(int q : queries){\n            res.push_back(depthAfterRemoveOf[q]);\n        }\n        return res;\n    }\n};\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/f2af07a9-458a-4e41-92a4-16f24885d65d_1729961271.8846073.png)\n
['Array', 'Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'C++']