C++ | Java | Simple solution using DFS and Hashmap
\n# Approach\n Describe your approach to solving the problem. \n- First i will find out the parent of all the nodes and will keep this information in a hashmap.
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- First i will find out the parent of all the nodes and will keep this information in a hashmap.\n- I am using a function named `dfs2` Which will take two parameter `root` and `k`. The task of this function is to store all the nodes at distance `k` from `root` in the subtree of `root` into answer list.\n- Now calling the functions `dfs2(target, k)`, `dfs2(parent(target), k-1)`, `dfs2(parent(parent(target)), k-2)`.... This will store all the nodes at distance `k` from `target` into answer list.\n- To avoide wrong insertion and TLE i am using a `vis` set which will keep track of already visited nodes.\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# C++ 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    unordered_map<TreeNode*, TreeNode*> par;\n    vector<int> ans;\n    unordered_set<TreeNode*> vis;\n    void dfs1(TreeNode* root, TreeNode* parent)\n    {\n        if(root==NULL)\n            return;\n\n        par[root]=parent;\n\n        dfs1(root->left, root);\n        dfs1(root->right, root);\n    }\n    void dfs2(TreeNode* root, int k)\n    {\n        if(root==NULL)\n            return;\n        if(vis.count(root))\n        {\n            return;\n        }\n\n\n        vis.insert(root);\n        if(k==0)\n        {\n            ans.push_back(root->val);\n            return;\n        }\n\n        dfs2(root->left, k-1);\n        dfs2(root->right, k-1);\n    }\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        \n        //Finding parent node\n        dfs1(root, NULL);\n        dfs2(target, k);\n        TreeNode* parent=par[target];\n        k--;\n        while(parent!=NULL && k>=0)\n        {\n            dfs2(parent, k);\n            parent=par[parent];\n            k--;\n        }\n        return ans;\n    }\n};\n```\n\n# Java Code\n```\nclass Solution {\n    HashMap<TreeNode,TreeNode> par=new HashMap<>();\n    List<Integer> ans=new ArrayList<>();\n    Set<TreeNode> vis=new HashSet<>();\n    \n    void dfs2(TreeNode root,int k)\n    {\n        if(root==null) return;\n        if(vis.contains(root)) return;\n        vis.add(root);\n        if(k==0)\n        {\n            ans.add(root.val);\n            return;\n        }\n        dfs2(root.left,k-1);\n        dfs2(root.right,k-1);\n    }\n    \n    void dfs1(TreeNode root,TreeNode parent)\n    {\n        if(root==null) return;\n        par.put(root,parent);\n        dfs1(root.left,root);\n        dfs1(root.right,root);\n    }\n    \n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        dfs1(root,null);\n        dfs2(target,k);\n        TreeNode parent=par.get(target);\n        k--;\n        while(parent!=null && k>=0)\n        {\n            dfs2(parent,k);\n            parent=par.get(parent);\n            k--;\n        }\n        return ans;\n    }\n}\n```
['Tree', 'Depth-First Search', 'C++', 'Java']