All Nodes Distance K in Binary Tree

1public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
2    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
3
4    buildParent(root, null, parentMap);
5
6    // BFS from target
7    Queue<TreeNode> queue = new LinkedList<>();
8    Set<TreeNode> visited = new HashSet<>();
9    queue.offer(target);
10    visited.add(target);
11    int dist = 0;
12
13    while (!queue.isEmpty() && dist < k) {
14        int levelSize = queue.size();
15
16        for (int i = 0; i < levelSize; i++) {
17            TreeNode current = queue.poll();
18
19            // Get neighbors: left, right, parent
20            List<TreeNode> neighbors = new ArrayList<>();
21            if (current.left != null) {
22                neighbors.add(current.left);
23            }
24            if (current.right != null) {
25                neighbors.add(current.right);
26            }
27            if (parentMap.containsKey(current)) {
28                neighbors.add(parentMap.get(current));
29            }
30
31            for (TreeNode neighbor : neighbors) {
32                if (!visited.contains(neighbor)) {
33                    visited.add(neighbor);
34                    queue.offer(neighbor);
35                }
36            }
37        }
38
39        dist++;
40    }
41
42    List<Integer> result = new ArrayList<>();
43    for (TreeNode node : queue) {
44        result.add(node.val);
45    }
46    return result;
47}
48
49private void buildParent(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {
50    if (node == null) {
51        return;
52    }
53    if (parent != null) {
54        parentMap.put(node, parent);
55    }
56    buildParent(node.left, node, parentMap);
57    buildParent(node.right, node, parentMap);
58}