C++ Solution || Concept in pictorial form ||  Using HASHMAPS and DFS
Intuition\nWe have to find the taget node and trace all elements which are exactly k distance away from it.\nK distance could be in following 3 directions - \ni
# Intuition\nWe have to find the taget node and trace all elements which are exactly k distance away from it.\nK distance could be in following 3 directions - \ni. Left node \nii. Right Node\niii. Either left or right of its parent node or parent\'s parent node, etc....\n\n# Approach\nLets view this poblem from frame of refernce of target node.\n\nThsi simpy means that we have to traverse the tree from target node only.\n\nThis is shown in the figure given below.\n\n\n![Screenshot 2023-06-28 154420.png](https://assets.leetcode.com/users/images/b1b3c93e-6047-43a7-bf39-56ea85424714_1687947295.7747242.png)\n\n![image.png](https://assets.leetcode.com/users/images/2dc8e8e3-7082-4f8d-8f7a-781fef3e8300_1687947221.5781527.png)\n\n\nSo, we have to traverse in three directions:-\n1. Parent \n2. Left Child\n3. Right Child\n\nBut still there is 1 problem of infinite looping between two nodes,for example let we are node x, than we may go to its left or right child. \n\nFrom that right or left child we may again go to its parent, and this process goes on and there would be an infinite looping.\n\n![Screenshot 2023-06-28 155436.png](https://assets.leetcode.com/users/images/d4f13e5a-ee18-4e1a-89c5-e05a49b5a78c_1687947912.3540056.png)\n\n\nThis situation can be easily handled by taking an extra variable for previous node from which current node is directed.\n\nSo, now by just a simple DFS, we can have all node \n\n\n\n\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n\nclass Solution {\n    map<TreeNode*, TreeNode*> m;\n    vector<int> ans;\n    void makeParent(TreeNode* root, TreeNode* parent){\n        if(root==NULL)return;\n        m[root]=parent;\n        makeParent(root->left,root);\n        makeParent(root->right,root);\n    }\n\n    void dfs(TreeNode* root,int k, TreeNode* prev){\n        if(root==NULL)return ;\n        if(k==0){\n            ans.push_back(root->val);\n            return;\n        }\n        if(root->left!=prev)dfs(root->left,k-1,root);\n        if(root->right!=prev)dfs(root->right,k-1,root);\n        if(m[root]!=prev)dfs(m[root],k-1,root);\n    }\n\n\npublic:\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        makeParent(root,NULL);\n        dfs(target,k,NULL);\n        return ans;\n;    }\n};\n```
['C++']