Beats 100 || Easy C++ Solution Using Bfs and Map
Intuition\nThe approach involves performing a breadth-first search (BFS) starting from the target node, while keeping track of the parent nodes. We first constr
# Intuition\nThe approach involves performing a breadth-first search (BFS) starting from the target node, while keeping track of the parent nodes. We first construct a map to store the parent-child relationships. Then, we perform BFS starting from the target node, marking visited nodes along the way. We decrement the distance `K` until it reaches 0, while considering the left child, right child, and parent nodes. Finally, we collect the nodes at distance `K` from the target node.\n\n# Approach\n1. Construct a map `parentMap` to store the parent-child relationships while traversing the tree.\n2. Perform BFS starting from the target node.\n3. Mark visited nodes using a map `visited`.\n4. Decrement the distance `K` until it reaches 0.\n5. At each level of BFS, consider the left child, right child, and parent nodes.\n6. Collect the nodes at distance `K` from the target node.\n7. Return the collected nodes.\n\n# Complexity\n- Time complexity: $$O(n)$$, where \\(n\\) is the number of nodes in the binary tree. We visit each node once during the BFS traversal.\n- Space complexity: $$O(n)$$, where \\(n\\) is the number of nodes in the binary tree. We use maps to store parent-child relationships and mark visited nodes. Additionally, the output vector may contain up to \\(n\\) nodes at distance \\(K\\) from the target node.\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        map<TreeNode*, TreeNode*> parentMap;\n        queue<TreeNode*> bfsQueue;\n        bfsQueue.push(root);\n        \n        // Construct parent-child relationships\n        while (!bfsQueue.empty()) {\n            TreeNode* current = bfsQueue.front();\n            bfsQueue.pop();\n            \n            // Assign parents to left child and right child if they exist\n            if (current->left) {\n                parentMap[current->left] = current;\n                bfsQueue.push(current->left);\n            }\n            \n            if (current->right) {\n                parentMap[current->right] = current;\n                bfsQueue.push(current->right);\n            }\n        }\n        \n        map<TreeNode*, bool> visited;\n        queue<TreeNode*> nodeQueue;\n        nodeQueue.push(target);\n        visited[target] = true;\n        \n        // Perform BFS from the target node\n        while (!nodeQueue.empty()) {\n            if (K == 0) break;\n            K--;\n            int size = nodeQueue.size();\n            for (int i = 0; i < size; i++) {\n                TreeNode* current = nodeQueue.front();\n                nodeQueue.pop();\n                \n                // Add unvisited left child to the queue\n                if (current->left && !visited[current->left]) {\n                    nodeQueue.push(current->left);\n                    visited[current->left] = true; \n                }\n                \n                // Add unvisited right child to the queue\n                if (current->right && !visited[current->right]) {\n                    nodeQueue.push(current->right);\n                    visited[current->right] = true;\n                }\n                \n                // Add unvisited parent node to the queue\n                if (parentMap[current] && !visited[parentMap[current]]) {\n                    nodeQueue.push(parentMap[current]);\n                    visited[parentMap[current]] = true; \n                }\n            }\n        }\n        \n        // Collect the nodes at distance K from the target node\n        vector<int> result;\n        while (!nodeQueue.empty()) {\n            result.push_back(nodeQueue.front()->val);\n            nodeQueue.pop();\n        }\n        \n        return result;\n    }\n};\n```
['Tree', 'Breadth-First Search', 'Ordered Map', 'Binary Tree', 'C++']