C++✅✅ | Faster than 90% of Sol^n | Using BFS & DFS(store parent of each node) | Clean and Concise😇
Code\n\n# PLEASE DO UPVOTE !\n\nCONNECT WITH ME ON LINKEDIN : https://www.linkedin.com/in/kunal-shaw-/\n\nImportant points to remember while giving a try to thi
# Code\n\n# **PLEASE DO UPVOTE !**\n\n**CONNECT WITH ME ON LINKEDIN : https://www.linkedin.com/in/kunal-shaw-/**\n\nImportant points to remember while giving a try to this problem !\n-> Start a BFS from root\n-> Traverse to left,right and to its parent\n-> Store the parent of each node in a unordered_map using simple DFS\n-> Store all the values present in level cnt==k in a vector ans and simply return it.\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    unordered_map<TreeNode*, TreeNode*> mp;\n    void dfs(TreeNode* root, TreeNode* parent){\n        if(!root) return;\n        if(!parent) parent = root;\n        else mp[root] = parent;\n        dfs(root->left, root);\n        dfs(root->right, root);\n    }\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        queue<TreeNode*> q;\n        set<TreeNode*> st;\n        dfs(root,NULL);\n        q.push(target);\n        int cnt=0;\n        vector<int> res;\n        while(!q.empty()){\n            int sz=q.size();\n            if(cnt>k) break;\n            while(sz--){\n                auto node=q.front();\n                q.pop();\n                if(node->left!=NULL and !st.count(node->left)){\n                    q.push(node->left);\n                    st.insert(node->left);\n                }\n                if(node->right!=NULL and !st.count(node->right)){\n                    q.push(node->right);\n                    st.insert(node->right);\n                }\n                if(mp.count(node) and !st.count(mp[node])){\n                    q.push(mp[node]);\n                    st.insert(mp[node]);\n                }\n                st.insert(node);\n                if(cnt==k){\n                    res.push_back(node->val);\n                }\n            }\n            cnt++;\n        }\n        return res;\n    }\n};\n```\n![memer-cat.jpg](https://assets.leetcode.com/users/images/dfc2018d-01d8-43da-9889-af2896179f15_1675779280.3429081.jpeg)\n\n
['Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Ordered Set', 'C++']