C++ | BFS | 4ms | EXPLAINED
\tIf we just need to find the nodes at distance K from a target node in child nodes, \n\tthen it is pretty easy. But here we need to find all the nodes at dista
\tIf we just need to find the nodes at distance K from a target node in child nodes, \n\tthen it is pretty easy. But here we need to find all the nodes at distance K which means\n\tthat we need to search even in the parent nodes.\n\t\n\t1. We take the help of hash maps to traverse the whole tree and store the child->parent reln.\n\t\tThis will help us in knowing the parent of every child. This is how we can traverse upward.\n\t2. We use BFS to traverse the graph from target node to downwards and upwards for a \n\t\tdistance of K nodes. We can now easily traverse upwards (thanks to the hash above)\n\t3. We keep a visited map as well so that we dont traverse a node more than once.\n\nTime Complexity: O(n)\nSpace Complexity: O(n)\n\n```\nclass Solution {\npublic:\n\n\t// Recursive Function to get the "parents hash" where child->parent relationship is kept\n    void fill_parents(unordered_map <TreeNode*, TreeNode*>& parents, TreeNode* node){    \n        if (node == NULL)\n            return;\n        // store the child->parent relationship and iterate for the left child\n        if(node->left != NULL){\n            parents[node->left] = node;\n            fill_parents(parents, node->left);\n        }\n        // store the child->parent relationship and iterate for the right child\n        if(node->right != NULL){\n            parents[node->right] = node;\n            fill_parents(parents, node->right);\n        }\n    }\n    \n    // Function to get all nodes which are a distance K from target node.\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {\n        if (root == NULL)\n            return {};\n        \n        unordered_map <TreeNode*, TreeNode*> parents;\n        // Get the child->parent relationship in the "parents" map.\n        fill_parents(parents, root);\n        \n        // Hash to store the nodes which are already visited so we do not fall in an infinite loop\n        unordered_map<TreeNode*, bool> visited;\n\n        // Queue for BFS\n        queue<TreeNode*> q;\n\n        int currentLevel = 0;\n        q.push(target);\n        visited[target] = true;\n        \n        // Till the queue is empty\n        while(!q.empty()){\n\n        \t// If we are already at level \'K\', then we break since queue will have our distance K nodes\n        \t// otherwise increase the level\n        \tif (currentLevel == K){\n                break;\n            }\n            currentLevel++;\n\n        \t// Get the size of the queue.\n            int size = q.size();\n            \n            // For the size number of elements in the queue, keep trying to visit them and push in the queue\n            // This is needed because this will tell us the number of nodes which are at the same level.\n            // This is really important to understand that when the control comes here the number of elements\n            // in the queue are all at the same level. While the loop runs, it may increase but the \'size\' \n            // variable is still the same and it will stop. The new nodes which are added are all at the same level.\n            // NOTE:  Putting NULL marker after the level ends will not work here.\n            for(int i=0; i<size; i++) {\n                TreeNode* front = q.front();\n                visited[front] = true;\n                q.pop();\n\n                if (front->left && !visited[front->left]){\n                    q.push(front->left);\n                    visited[front->left] = true;\n                }\n\n                if (front->right && !visited[front->right]){\n                    q.push(front->right);\n                    visited[front->right] = true;\n                }\n\n                if (parents[front] && !visited[parents[front]]){\n                    q.push(parents[front]);\n                    visited[parents[front]] = true;\n                }\n            }\n        }\n        vector<int> res;\n        while(!q.empty()){\n            TreeNode *f = q.front();\n            q.pop();\n            res.push_back(f->val);\n        }\n        return res;\n    }\n};\n```
['Breadth-First Search', 'C', 'C++']