Simple Solution With Hindi Explanation || Beats : 80%✅ || Using DFS & BFS🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nHume tree main neeche bhi traverse karne ki power chahiye or saath hi saath upar traver
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nHume tree main neeche bhi traverse karne ki power chahiye or saath hi saath upar traverse karne ki bhi power chahiye. Hume neche traverse left or right node ki help se kar skte hain par upar traverse karne k liye hume map banana padega jo node dalne par uske parent ki value return kare.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHum DFS ka use karke map create karenge jo har node ke parent ki value find karega. Uske baad BFS ki help se hum target se start hote huye sare tree k nodes pr traverse karenge Up,Left,Right or each node visit karte huye level ko check karenge if level==k. Hum node->val ko ans array mai store kar denge.\n\nNOTE: Hume ek visited naam ki array/map banana hoga ye check karne k liye ki koi node pahle se visited hai ya nahi agar node visited nhi hai to queue mai push karke hum use visited mark kar denge jisse infinity loop (TLE) na aaye.\n\n\n# Complexity\n- Time complexity: O(n)\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/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\nclass Solution {\npublic:\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        vector<int> ans;\n        if (root==NULL) return ans;\n        map<int,bool> visited;\n        map<TreeNode*,TreeNode*> mp;\n        parent(root, mp);\n        queue<pair<TreeNode*,int>> q;\n        q.push({target,0});\n        visited[target->val]=1;\n        while(!q.empty()){\n            TreeNode* node =q.front().first;\n            int level =q.front().second;\n            q.pop();\n            if (level==k) ans.push_back(node->val);\n            if (level>k) break;\n            if (node->left && !visited[node->left->val]){\n                visited[node->left->val]=1;\n                q.push({node->left,level+1});\n            }\n            if (node->right && !visited[node->right->val]){\n                visited[node->right->val]=1;\n                q.push({node->right,level+1});\n            }\n            if (mp[node] &&!visited[mp[node]->val]){\n                visited[mp[node]->val]=1;\n                q.push({mp[node],level+1});\n            }\n            \n        }\n        return ans;\n    }\n    void parent(TreeNode* root, map<TreeNode*,TreeNode*> &mp){\n        if (root==NULL) return;\n        else {\n            if (root->left!=NULL) {\n                mp[root->left]=root;\n            }\n            if (root->right!=NULL) {\n                mp[root->right]=root;\n            }\n            parent(root->left,mp);\n            parent(root->right,mp);\n\n        }\n    }\n};\n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Queue', 'C++']