100% fast | BFS+DFS Both | C++| JAVA | PYTHON+ Video
Intuition\n\n Describe your first thoughts on how to solve this problem. \nTree question so it can be solved by DFS or BFS\n\nFor detailed explanation you can r
# Intuition\n\n<!-- Describe your first thoughts on how to solve this problem. -->\nTree question so it can be solved by DFS or BFS\n\nFor detailed explanation you can refer to my youtube channel (hindi Language)\nhttps://youtu.be/w6r6OHPFzbc\n or link in my profile.Here,you can find any solution in playlists monthwise from June 2023 with detailed explanation.i upload daily leetcode solution video with short and precise explanation (5-10) minutes.\nor\nsearch \uD83D\uDC49All Nodes Distance K in Binary Tree by Let\'s Code Together on youtube\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n\n1. First, create an unordered map `parent` to store the parent node of each node in the binary tree.\n2. Use the `getparentbyDFS` or `getparentbyBFS` function to populate the `parent` map by performing a depth-first traversal or bredth first search of the binary tree.\n3. Initialize a queue `q` and an unordered map `vis` to keep track of visited nodes.\n4. Mark the target node as visited by setting `vis[target]` to `true` and push it into the queue.\n5. Perform a BFS traversal while the queue is not empty:\n   a. Retrieve the front node `curr` from the queue.\n   b. If the current node\'s left child exists and has not been visited, mark it as visited, and push it into the queue.\n   c. If the current node\'s right child exists and has not been visited, mark it as visited, and push it into the queue.\n   d. If the parent of the current node exists and has not been visited, mark it as visited, and push it into the queue.\n   e. Repeat steps a to d for all nodes at the current level.\n   f. Increment the level `lev` by 1.\n   g. If the current level is equal to `k`, exit the traversal.\n6. Store the nodes in the queue in a vector `ans`.\n7. Return the vector `ans`, which contains all the nodes at a distance of `k` from the target node.\n\n\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# Code\n```C++ []\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    void getparentbyBFS(unordered_map<TreeNode*,TreeNode*>&parent,TreeNode*root){\n        queue<TreeNode*>q;\n        q.push(root);\n        while(!q.empty()){\n            int n=q.size();\n            while(n--){\n                TreeNode*curr=q.front();\n                q.pop();\n                if(curr->left){\n                    parent[curr->left]=curr;\n                    q.push(curr->left);\n                }\n                if(curr->right){\n                      parent[curr->right]=curr;\n                    q.push(curr->right);\n                }\n            }\n        }\n    }\n   void getparentbyDFS(unordered_map<TreeNode*,TreeNode*>&parent,TreeNode*root){\n       if(root==NULL)\n       return;\n       if(root->left!=NULL){\n         parent[root->left]=root;\n       }\n       if(root->right!=NULL){\n           parent[root->right]=root;\n       }\n       getparentbyDFS(parent,root->left);\n        getparentbyDFS(parent,root->right);\n   }\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        unordered_map<TreeNode*,TreeNode*>parent;\n        getparentbyDFS(parent,root);\n        queue<TreeNode*>q;\n        unordered_map<TreeNode*,bool>vis;\n        vis[target]=true;\n        q.push(target);\n        int lev=0;\n        while(!q.empty()){\n            int n=q.size();\n            if(lev==k)\n                break;\n            lev++;\n            while(n--){\n                TreeNode*curr=q.front();\n                q.pop();\n                if(curr->left&&!vis[curr->left]){\n                    vis[curr->left]=true;\n                    q.push(curr->left);\n                }\n                 if(curr->right&&!vis[curr->right]){\n                    vis[curr->right]=true;\n                    q.push(curr->right);\n                }\n                if(parent[curr]&&!vis[parent[curr]]){\n                    vis[parent[curr]]=true; \n                    q.push(parent[curr]);\n                }\n            }\n        }\n        vector<int>ans;\n        while(q.size()>0){\n            ans.push_back(q.front()->val);\n            q.pop();\n        }\n        return ans;\n    }\n};\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public void getParentsByBFS(Map<TreeNode, TreeNode> parent, TreeNode root) {\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n        while (!queue.isEmpty()) {\n            int n = queue.size();\n            while (n-- > 0) {\n                TreeNode curr = queue.poll();\n                if (curr.left != null) {\n                    parent.put(curr.left, curr);\n                    queue.offer(curr.left);\n                }\n                if (curr.right != null) {\n                    parent.put(curr.right, curr);\n                    queue.offer(curr.right);\n                }\n            }\n        }\n    }\n\n    public void getParentsByDFS(Map<TreeNode, TreeNode> parent, TreeNode root) {\n        if (root == null)\n            return;\n        if (root.left != null)\n            parent.put(root.left, root);\n        if (root.right != null)\n            parent.put(root.right, root);\n        getParentsByDFS(parent, root.left);\n        getParentsByDFS(parent, root.right);\n    }\n\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        Map<TreeNode, TreeNode> parent = new HashMap<>();\n        getParentsByDFS(parent, root);\n        Queue<TreeNode> queue = new LinkedList<>();\n        Map<TreeNode, Boolean> visited = new HashMap<>();\n        visited.put(target, true);\n        queue.offer(target);\n        int level = 0;\n        while (!queue.isEmpty()) {\n            int n = queue.size();\n            if (level == k)\n                break;\n            level++;\n            while (n-- > 0) {\n                TreeNode curr = queue.poll();\n                if (curr.left != null && !visited.containsKey(curr.left)) {\n                    visited.put(curr.left, true);\n                    queue.offer(curr.left);\n                }\n                if (curr.right != null && !visited.containsKey(curr.right)) {\n                    visited.put(curr.right, true);\n                    queue.offer(curr.right);\n                }\n                if (parent.containsKey(curr) && !visited.containsKey(parent.get(curr))) {\n                    visited.put(parent.get(curr), true);\n                    queue.offer(parent.get(curr));\n                }\n            }\n        }\n        List<Integer> ans = new ArrayList<>();\n        while (!queue.isEmpty()) {\n            ans.add(queue.poll().val);\n        }\n        return ans;\n    }\n}\n\n```\n```Python []\nfrom collections import deque\n\nclass Solution:\n    def getParentsByBFS(self, parent, root):\n        queue = deque()\n        queue.append(root)\n        while queue:\n            n = len(queue)\n            while n > 0:\n                curr = queue.popleft()\n                if curr.left:\n                    parent[curr.left] = curr\n                    queue.append(curr.left)\n                if curr.right:\n                    parent[curr.right] = curr\n                    queue.append(curr.right)\n                n -= 1\n    \n    def getParentsByDFS(self, parent, root):\n        if not root:\n            return\n        if root.left:\n            parent[root.left] = root\n        if root.right:\n            parent[root.right] = root\n        self.getParentsByDFS(parent, root.left)\n        self.getParentsByDFS(parent, root.right)\n    \n    def distanceK(self, root, target, k):\n        parent = {}\n        self.getParentsByDFS(parent, root)\n        queue = deque()\n        visited = {target: True}\n        queue.append(target)\n        level = 0\n        while queue:\n            n = len(queue)\n            if level == k:\n                break\n            level += 1\n            while n > 0:\n                curr = queue.popleft()\n                if curr.left and curr.left not in visited:\n                    visited[curr.left] = True\n                    queue.append(curr.left)\n                if curr.right and curr.right not in visited:\n                    visited[curr.right] = True\n                    queue.append(curr.right)\n                if curr in parent and parent[curr] not in visited:\n                    visited[parent[curr]] = True\n                    queue.append(parent[curr])\n                n -= 1\n        ans = []\n        while queue:\n            ans.append(queue.popleft().val)\n        return ans\n\n```\n![upvote-this-you.jpg](https://assets.leetcode.com/users/images/8391c1f6-e09f-4ed0-8fa0-15250c121032_1689041773.5203698.jpeg)\n
['Tree', 'Depth-First Search', 'Breadth-First Search', 'C++', 'Java']