✅Two BFS || C++ || JAVA || PYTHON || Beginner Friendly🔥🔥🔥
Intuition:\nThe Intuition is to perform two BFS traversals: one to build the parent-child relationship and another to find all nodes at a distance of k from the
# Intuition:\nThe Intuition is to perform two BFS traversals: one to build the parent-child relationship and another to find all nodes at a distance of k from the target node.\n\n# Explanation:\n\n1. Start a BFS from the root node of the binary tree. We will use a queue to perform the BFS traversal. Initialize an empty queue and push the root node into it.\n\n2. While the queue is not empty, perform the following steps:\n   - Get the current size of the queue (number of nodes at the current level).\n   - Iterate through all the nodes at the current level.\n   - For each node, check if it has a left child. If it does, store the parent-child relationship by mapping the left child\'s value to its parent node in an unordered_map called "parent".\n   - Similarly, if the current node has a right child, store the parent-child relationship for the right child.\n   - After processing the children of the current node, remove it from the queue.\n\n3. After the BFS traversal, we will have the parent-child relationship stored in the "parent" unordered_map.\n\n4. Now, we need to perform another BFS traversal to find all the nodes at a distance of k from the target node. Initialize another empty queue and push the target node into it.\n\n5. While the value of k is greater than 0 and the queue is not empty, perform the following steps:\n   - Get the current size of the queue (number of nodes at the current level).\n   - Iterate through all the nodes at the current level.\n   - Mark the current node as visited by adding its value to the "visited" unordered_map.\n   - If the current node has a left child and it has not been visited yet, push it into the queue.\n   - If the current node has a right child and it has not been visited yet, push it into the queue.\n   - If the current node has a parent and the parent node has not been visited yet, push the parent node into the queue.\n   - After processing the current node and its children/parent, remove it from the queue.\n\n6. After the BFS traversal, we will have all the nodes at a distance of k from the target node stored in the queue.\n\n7. Finally, we can extract the values of the nodes from the queue and store them in a vector called "ans". Return the "ans" vector as the result.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        vector<int> ans;\n        unordered_map<int, TreeNode*> parent;\n        queue<TreeNode*> q;\n        q.push(root);\n\n        while(!q.empty()){\n            int si = q.size();\n            for(int i = 0; i < si; i++){\n                auto top = q.front();\n                q.pop();\n                \n                if(top -> left){\n                    parent[top->left->val] = top;\n                    q.push(top->left); \n                }\n\n                if(top -> right){\n                    parent[top->right->val] = top;\n                    q.push(top->right); \n                }\n            }\n        }\n\n        unordered_map<int, int> visited;\n        q.push(target);\n        while(k-- && !q.empty()){\n            int size = q.size();\n\n            for(int i = 0; i < size; i++){\n                auto top = q.front();\n                q.pop();\n\n                visited[top -> val] = 1;\n\n                if(top -> left && !visited[top->left->val]){\n                    q.push(top -> left);\n                }\n\n                if(top -> right && !visited[top->right->val]){\n                    q.push(top -> right);\n                }\n\n                if(parent[top->val] && !visited[parent[top->val] -> val]){\n                    q.push(parent[top->val]);\n                }\n\n            }\n        }\n\n        while(!q.empty()){\n            ans.push_back(q.front()->val);\n            q.pop();\n        }\n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        List<Integer> ans = new ArrayList<>();\n        Map<Integer, TreeNode> parent = new HashMap<>();\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            for (int i = 0; i < size; i++) {\n                TreeNode top = queue.poll();\n\n                if (top.left != null) {\n                    parent.put(top.left.val, top);\n                    queue.offer(top.left);\n                }\n\n                if (top.right != null) {\n                    parent.put(top.right.val, top);\n                    queue.offer(top.right);\n                }\n            }\n        }\n\n        Map<Integer, Integer> visited = new HashMap<>();\n        queue.offer(target);\n        while (k > 0 && !queue.isEmpty()) {\n            int size = queue.size();\n\n            for (int i = 0; i < size; i++) {\n                TreeNode top = queue.poll();\n\n                visited.put(top.val, 1);\n\n                if (top.left != null && !visited.containsKey(top.left.val)) {\n                    queue.offer(top.left);\n                }\n\n                if (top.right != null && !visited.containsKey(top.right.val)) {\n                    queue.offer(top.right);\n                }\n\n                if (parent.containsKey(top.val) && !visited.containsKey(parent.get(top.val).val)) {\n                    queue.offer(parent.get(top.val));\n                }\n            }\n\n            k--;\n        }\n\n        while (!queue.isEmpty()) {\n            ans.add(queue.poll().val);\n        }\n        return ans;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n        ans = []\n        parent = {}\n        queue = deque()\n        queue.append(root)\n\n        while queue:\n            size = len(queue)\n            for _ in range(size):\n                top = queue.popleft()\n\n                if top.left:\n                    parent[top.left.val] = top\n                    queue.append(top.left)\n\n                if top.right:\n                    parent[top.right.val] = top\n                    queue.append(top.right)\n\n        visited = {}\n        queue.append(target)\n        while k > 0 and queue:\n            size = len(queue)\n\n            for _ in range(size):\n                top = queue.popleft()\n\n                visited[top.val] = 1\n\n                if top.left and top.left.val not in visited:\n                    queue.append(top.left)\n\n                if top.right and top.right.val not in visited:\n                    queue.append(top.right)\n\n                if top.val in parent and parent[top.val].val not in visited:\n                    queue.append(parent[top.val])\n\n            k -= 1\n\n        while queue:\n            ans.append(queue.popleft().val)\n\n        return ans\n```\n\n**If you found my solution helpful, I would greatly appreciate your upvote, as it would motivate me to continue sharing more solutions.**\n\n
['Breadth-First Search', 'C++', 'Java', 'Python3']