C++✅✅ | Faster than 80%🚀| Explained⭐ + Commented⭐ | DFS🍀 | Clean Code |
PLEASE DO UPVOTE!!!!!\n\nCONNECT WITH ME ON LINKEDIN :  https://www.linkedin.com/in/md-kamran-55b98521a/\n\n\n# Intuition\nTo Find paths between Nodes we Use BF
# PLEASE DO UPVOTE!!!!!\n\n**CONNECT WITH ME ON LINKEDIN :  https://www.linkedin.com/in/md-kamran-55b98521a/**\n\n\n# Intuition\n**To Find paths between Nodes we Use BFS(Breadth First Search), for than we should have a mapping between a node(parent) and its Childs by DFS(Depth First Search). By BFS we explore all Nodes at a Distance K, and store each of them in the Answer Vector**\n\n# Approach\n**1. Store Parent Child Mapped Pairs Using DFS**\n**2. Apply BFS starting from Target**\n**3. Store all nodes at a distance of K**\n\n\n\n# Code\n```\n\nclass Solution {\npublic:\n\nunordered_map<TreeNode*,TreeNode*>mpp;\n\nvoid Parent_Child(TreeNode* Child, TreeNode* Parent)\n{\n  if(Child == NULL) return;\n  if(Parent == NULL) Parent = Child;\n  else mpp[Child] = Parent;\n  Parent_Child(Child->left, Child);\n  Parent_Child(Child->right, Child);\n}\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n      \n      Parent_Child(root, NULL); //as root has no parent so parent is NULL\n      queue<TreeNode*>q;\n      unordered_set<TreeNode*>visited; // to keep mark of visited nodes so that we dont consider it again\n      vector<int>ans;\n      \n      q.push(target); //pushing target, so to explore nodes around target \n      visited.insert(target);\n      int distance = 0;\n\n      while(!q.empty())\n      {\n         int size = q.size();\n         for(int i = 0; i < size; ++i)\n         {\n           auto temp = q.front(); //Current Node\n           auto Left_Child = temp->left; //Left child\n           auto Right_Child = temp->right; //Right Child\n           q.pop();\n\n           if(Left_Child != NULL && visited.count(Left_Child) == 0) \n           {\n             q.push(Left_Child);\n             visited.insert(Left_Child);\n           }\n\n           if(Right_Child != NULL && visited.count(Right_Child) == 0)\n           {\n             q.push(Right_Child);\n             visited.insert(Right_Child);\n           }\n\n           if(mpp[temp] && visited.count(mpp[temp])==0)\n           {\n               q.push(mpp[temp]);\n               visited.insert(mpp[temp]);\n           }\n\n           if(distance == k) ans.push_back(temp -> val);\n         }\n          distance++;\n          if(distance > k) break; // if distace exceeds k, there\'s no need to go furthur\n      } \n      return ans; \n    }\n};\n\n```\n![b62ab1be-232a-438f-9524-7d8ca4dbd5fe_1675328166.1161866.png](https://assets.leetcode.com/users/images/8d5343b1-0eb4-4111-a914-40ce968fd034_1675389764.2273676.png)
['Hash Table', 'Depth-First Search', 'Breadth-First Search', 'C++']