All nodes distance K in Binary Tree

77.All Nodes Distance K in Binary Tree

Tree

Breadth-First Search

Problem Statement:

Given the root of a binary tree, a target node, and an integer K, return the values of all nodes that are a distance K from the target node. The values should be returned as a list in any order.

Algorithm:

1. Use a Map to store connections between nodes (parent-child relationships).
2. Perform a breadth-first search (BFS) starting from the target node:
• Use a queue to explore nodes level by level.
• Track visited nodes to prevent revisiting.
3. When the distance reaches K, collect all nodes at this level.
4. Return the collected nodes as the result.

Complexity:

Time: O(n) | Space: O(n)

Java Implementation:

class Solution {
    Map> map = new HashMap<>();

    public List distanceK(TreeNode root, TreeNode target, int K) {
        List res = new ArrayList<>();
        if (root == null || K < 0) return res;
        buildMap(root, null);
        if (!map.containsKey(target)) return res;
        
        Set visited = new HashSet<>();
        Queue q = new LinkedList<>();
        q.add(target);
        visited.add(target);

        while (!q.isEmpty()) {
            int size = q.size();
            if (K == 0) {
                for (int i = 0; i < size; i++) res.add(q.poll().val);
                return res;
            }
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                for (TreeNode next : map.get(node)) {
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    q.add(next);
                }
            }
            K--;
        }
        return res;
    }

    private void buildMap(TreeNode node, TreeNode parent) {
        if (node == null) return;
        if (!map.containsKey(node)) {
            map.put(node, new ArrayList<>());
            if (parent != null) {
                map.get(node).add(parent);
                map.get(parent).add(node);
            }
            buildMap(node.left, node);
            buildMap(node.right, node);
        }
    }
}

Python Implementation:

from collections import defaultdict, deque

class Solution:
    def distanceK(self, root, target, K):
        def build_map(node, parent):
            if not node:
                return
            if parent:
                graph[node].append(parent)
                graph[parent].append(node)
            build_map(node.left, node)
            build_map(node.right, node)

        graph = defaultdict(list)
        build_map(root, None)

        visited = set()
        queue = deque([target])
        visited.add(target)

        for _ in range(K):
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

        return [node.val for node in queue]

C++ Implementation:

#include 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    vector distanceK(TreeNode* root, TreeNode* target, int K) {
        unordered_map> graph;
        buildGraph(root, nullptr, graph);

        unordered_set visited;
        queue q;
        q.push(target);
        visited.insert(target);

        for (int level = 0; level < K; level++) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                for (TreeNode* neighbor : graph[node]) {
                    if (!visited.count(neighbor)) {
                        visited.insert(neighbor);
                        q.push(neighbor);
                    }
                }
            }
        }

        vector result;
        while (!q.empty()) {
            result.push_back(q.front()->val);
            q.pop();
        }
        return result;
    }

private:
    void buildGraph(TreeNode* node, TreeNode* parent, unordered_map>& graph) {
        if (!node) return;
        if (parent) {
            graph[node].push_back(parent);
            graph[parent].push_back(node);
        }
        buildGraph(node->left, node, graph);
        buildGraph(node->right, node, graph);
    }
};