BFS of the equivalent graph | C++ | Easy to understand | Clean codes | Striver
Intuition\nAs I saw the line that return the nodes which are at a distance of K from target node, my mind jumped to BFS, as in BFS each time we iterate over the
# *Intuition*\nAs I saw the line that return the nodes which are at a distance of K from target node, my mind jumped to BFS, as in BFS each time we iterate over the graph\'s nodes we go on level wise. \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# ***Approach***\nFirst of all we have to make the graph to apply BFS algorithm on it. For doing so we need to create an adjacency list. But what should be the size of the list? Simply make the list of size that equals to the upper limit of nodes (here 500). \n\nNow to make the graph I have made a separate recursive function called "makeGraph" in which I just checked if there is a left node of the graph and if there is a right node of the graph, if so then simply make 2 undirected edges for the nodes and then recusively call the function for the left and right child.\nThe base case is when we call the function for a NULL, simply return if a call is made for NULL.\n\nNow that we have made the graph, we are ready to apply our BFS algorithm on it. So declare the essential Data Structures for the BFS algorithm which include the queue and the visited array(to make sure that we do not go in a loop).\n\n Now make a variable level and initialize it to 0, level will tell us the level on which we are currently. Now as the BFS runs the level increses by one each time. Whenever the level is equals to K, along with pushing the nodes into the queue: we also put them in our answer array. Also maintain a flag variable so that we do not iterate after the level \'K\'.\n\nAt last return the answer array. \n<!-- Describe your approach to solving the problem. -->\n\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\nvector<int> adj[501];\n\nvoid makeGraph(TreeNode* root){\n    if(!root) return;\n    if(root->left){\n        adj[root->val].push_back(root->left->val);\n        adj[root->left->val].push_back(root->val);\n    }\n    if(root->right){\n        adj[root->val].push_back(root->right->val);\n        adj[root->right->val].push_back(root->val);\n    }\n    makeGraph(root->left);\n    makeGraph(root->right);\n}\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        vector<int> ans;\n        if(k==0){\n            ans.push_back(target->val);\n            return ans;\n        }\n        makeGraph(root);\n        queue<int> q;\n        int flag=0;\n        vector<int> vis(501,0);\n        q.push(target->val);\n        vis[target->val]=1;\n        int level=0;\n        while(!q.empty()){\n            int size=q.size();\n            level++;\n            for(int i=0;i<size;i++){\n                int node=q.front();\n                for(auto x:adj[node]){\n                    if(!vis[x]){\n                        vis[x]=1;\n                        q.push(x);\n                        if(level==k){\n                            flag=1;\n                            ans.push_back(x);\n                        }\n                    }\n                }\n                q.pop();\n            }\n            if(flag==1) break;\n        }\n        return ans;\n    }\n};\n```\n# *Please upvote if this helped!*\n
['C++']