Python 🔥Java 🔥C++ 🔥Simple Solution 🔥Easy to Understand
An Upvote will be encouraging \uD83D\uDC4D\n\n# Video Solution\n\n# Search \uD83D\uDC49 All Nodes Distance K in Binary Tree By Tech Wired\n\n# OR\n\n# Click the
# An Upvote will be encouraging \uD83D\uDC4D\n\n# Video Solution\n\n# Search \uD83D\uDC49 `All Nodes Distance K in Binary Tree By Tech Wired`\n\n# OR\n\n# Click the link in my profile\n\n# Intuition\n\n\n- First, we build an adjacency list graph representation of the binary tree. Each node in the graph is mapped to a list of its neighbors (parent and child nodes).\n- Next, we start a BFS from the target node. We maintain a queue to perform the BFS and a set to keep track of visited nodes.\n- During the BFS, we traverse the tree in a level-by-level manner, keeping track of the distance of each visited node from the target node.\n- Whenever we encounter a node at distance K from the target node, we add its value to the result list.\n- If the distance exceeds K, we break the BFS loop since nodes beyond distance K are not required.\n- For each node, we enqueue its unvisited neighbors and continue the BFS process until the queue is empty.\n- Finally, we return the result list containing the values of the nodes at distance K from the target node.\n\n```Python []\nclass Solution:\n    def distanceK(self, root, target, K):\n        # Step 1: Build adjacency list graph\n        graph = {}\n        self.buildGraph(root, None, graph)\n\n        # Step 2: Perform BFS from the target node\n        queue = [(target, 0)]\n        visited = set([target])\n        result = []\n        \n        while queue:\n            node, distance = queue.pop(0)\n            \n            if distance == K:\n                result.append(node.val)\n                \n            if distance > K:\n                break\n            \n            for neighbor in graph[node]:\n                if neighbor not in visited:\n                    visited.add(neighbor)\n                    queue.append((neighbor, distance + 1))\n        \n        return result\n    \n    def buildGraph(self, node, parent, graph):\n        if not node:\n            return\n        \n        if node not in graph:\n            graph[node] = []\n            \n        if parent:\n            graph[node].append(parent)\n            graph[parent].append(node)\n            \n        self.buildGraph(node.left, node, graph)\n        self.buildGraph(node.right, node, graph)\n\n```\n```Java []\n\nclass Solution {\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        // Step 1: Build adjacency list graph\n        Map<TreeNode, List<TreeNode>> graph = new HashMap<>();\n        buildGraph(root, null, graph);\n\n        // Step 2: Perform BFS from the target node\n        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();\n        Set<TreeNode> visited = new HashSet<>();\n        List<Integer> result = new ArrayList<>();\n        \n        queue.add(new Pair<>(target, 0));\n        visited.add(target);\n        \n        while (!queue.isEmpty()) {\n            Pair<TreeNode, Integer> pair = queue.poll();\n            TreeNode node = pair.getKey();\n            int distance = pair.getValue();\n            \n            if (distance == K) {\n                result.add(node.val);\n            }\n            \n            if (distance > K) {\n                break;\n            }\n            \n            for (TreeNode neighbor : graph.get(node)) {\n                if (!visited.contains(neighbor)) {\n                    visited.add(neighbor);\n                    queue.add(new Pair<>(neighbor, distance + 1));\n                }\n            }\n        }\n        \n        return result;\n    }\n    \n    private void buildGraph(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> graph) {\n        if (node == null) {\n            return;\n        }\n        \n        if (!graph.containsKey(node)) {\n            graph.put(node, new ArrayList<>());\n        }\n        \n        if (parent != null) {\n            graph.get(node).add(parent);\n            graph.get(parent).add(node);\n        }\n        \n        buildGraph(node.left, node, graph);\n        buildGraph(node.right, node, graph);\n    }\n}\n\n```\n```C++ []\n\nclass Solution {\npublic:\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {\n        // Step 1: Build adjacency list graph\n        unordered_map<TreeNode*, vector<TreeNode*>> graph;\n        buildGraph(root, nullptr, graph);\n\n        // Step 2: Perform BFS from the target node\n        queue<pair<TreeNode*, int>> q;\n        unordered_set<TreeNode*> visited;\n        vector<int> result;\n        \n        q.push({target, 0});\n        visited.insert(target);\n        \n        while (!q.empty()) {\n            TreeNode* node = q.front().first;\n            int distance = q.front().second;\n            q.pop();\n            \n            if (distance == K) {\n                result.push_back(node->val);\n            }\n            \n            if (distance > K) {\n                break;\n            }\n            \n            for (TreeNode* neighbor : graph[node]) {\n                if (visited.find(neighbor) == visited.end()) {\n                    visited.insert(neighbor);\n                    q.push({neighbor, distance + 1});\n                }\n            }\n        }\n        \n        return result;\n    }\n    \n    void buildGraph(TreeNode* node, TreeNode* parent, unordered_map<TreeNode*, vector<TreeNode*>>& graph) {\n        if (node == nullptr) {\n            return;\n        }\n        \n        if (graph.find(node) == graph.end()) {\n            graph[node] = vector<TreeNode*>();\n        }\n        \n        if (parent != nullptr) {\n            graph[node].push_back(parent);\n            graph[parent].push_back(node);\n        }\n        \n        buildGraph(node->left, node, graph);\n        buildGraph(node->right, node, graph);\n    }\n};\n\n```\n# An Upvote will be encouraging \uD83D\uDC4D
['Breadth-First Search', 'C++', 'Java', 'Python3']