C++ Solution 🔥Using BFS Traversal🔥 With Explaination🔥
Explaination\n\n1. Create a queue named q to perform level order traversal of the tree.\n2. Create an unordered map named parent to store the parent-child relat
# Explaination\n\n1. Create a queue named `q` to perform level order traversal of the tree.\n2. Create an unordered map named `parent` to store the parent-child relationships of nodes in the tree.\n3. Push the root node of the tree into the queue.\n4. Perform a level order traversal using the queue until it becomes empty:\n   a. Dequeue the front node `front` from the queue.\n   b. If `front` has a left child, store the parent-child relationship in the `parent` map and enqueue the left child.\n   c. If `front` has a right child, store the parent-child relationship in the `parent` map and enqueue the right child.\n5. Create an unordered map named `visited` to keep track of visited nodes.\n6. Push the target node into the queue and mark it as visited in the `visited` map.\n7. Initialize a count `cnt` to 0 to track the distance from the target node.\n8. While the queue is not empty and the count `cnt` is less than or equal to `k`:\n   a. Increment `cnt`.\n   b. Get the size of the queue and iterate `size` times:\n      - Dequeue the front node `front` from the queue.\n      - If `front` has a left child and it has not been visited before, enqueue it and mark it as visited.\n      - If `front` has a right child and it has not been visited before, enqueue it and mark it as visited.\n      - If `front` has a parent (accessed using `parent[front]`) and it has not been visited before, enqueue it and mark it as visited.\n9. Create a vector named `ans` to store the values of the nodes at distance `k`.\n10. While the queue is not empty, dequeue the front node `front` from the queue and push its value into the `ans` vector.\n11. Return the `ans` vector containing the values of the nodes at distance `k` from the target node.\n\nBy following this approach, we can find the nodes at distance `k` from the target node in the binary tree.\n# Complexity\n- Time complexity: O(N), We are just traversing the nodes.\n\n- Space complexity: O(N), We use unordered_map to store the parent.\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    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        queue<TreeNode*> q;\n        unordered_map<TreeNode*,TreeNode*> parent;\n        q.push(root);\n\n        while(!q.empty()){\n            TreeNode*front=q.front();\n            q.pop();\n            if(front->left){\n                parent[front->left] = front;\n                q.push(front->left);\n            }\n            if(front->right){\n                parent[front->right] = front;\n                q.push(front->right);\n            }\n        }\n\n        unordered_map<TreeNode*,bool> visited;\n        q.push(target);\n        visited[target]=true;\n        int cnt=0;\n        while(!q.empty()){\n            if(cnt==k) break;\n            cnt++;\n            int size=q.size();\n            for(int i=0;i<size;i++){\n                TreeNode*front=q.front();\n                q.pop();\n                if(front->left  &&  !visited[front->left]){\n                    q.push(front->left);\n                    visited[front->left]=true;\n                }\n                if(front->right  &&  !visited[front->right]){\n                    q.push(front->right);\n                    visited[front->right]=true;\n                }\n                if(parent[front]  &&  !visited[ parent[front] ]){\n                    q.push( parent[front] );\n                    visited[parent[front]]=true;\n                }\n            }\n        }\n        vector<int> ans;\n        while(!q.empty()){\n            TreeNode*front=q.front();\n            q.pop();\n            ans.push_back( front->val );\n        }\n        return ans;\n    }\n};\n\n\n\n\n\n\n\n\n\n\n\n\n\n```
['Hash Table', 'Breadth-First Search', 'C++']