> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/print-all-nodes-at-distance-k-from-a-given-node.md).

# Print all nodes at distance k from a given node

We are given a binary tree (with root node `root`), a `target` node, and an integer value `K`.

Return a list of the values of all nodes that have a distance `K` from the `target` node.  The answer can be returned in any order.

**Example 1:**

```
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.
```

**Note:**

1. The given tree is non-empty.
2. Each node in the tree has unique values `0 <= node.val <= 500`.
3. The `target` node is a node in the tree.
4. `0 <= K <= 1000`.

```java
class Solution {
    List<Integer> ans;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        ans = new ArrayList<>();
        findKAway(root, target, K);
        return ans;
    }

    // Returning distance of root from target node
    public int findKAway(TreeNode node, TreeNode target, int k) {
        // -1 => Target not found
        if (node == null)
            return -1;
        if (node.val == target.val) {
            findKDown(node, k);
            return 0;
        }
        int distL = findKAway(node.left, target, k);
        if (distL != -1) {
            if (distL + 1 == k)
                ans.add(node.val);
            else if (k > distL + 1)
                findKDown(node.right, k - distL - 2);
            return 1 + distL;
        }
        int distR = findKAway(node.right, target, k);
        if (distR != -1) {
            if (distR + 1 == k)
                ans.add(node.val);
            else if (k > distR + 1)
                findKDown(node.left, k - distR - 2);
            return 1 + distR;
        }
        return -1;
    }

    public void findKDown(TreeNode node, int k) {
        if (node == null || k < 0)
            return;
        if (k == 0) {
            ans.add(node.val);
            return;
        }
        findKDown(node.left, k - 1);
        findKDown(node.right, k - 1);
    }
}
// Graph Solution O(N)
class Solution {
    List<Integer>[] graph;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        // Converting tree to undirected graph
        graph = new ArrayList[501];
        // Each node in the tree has unique values 0 <= node.val <= 500
        for (int i = 0; i <= 500; i++)
            graph[i] = new ArrayList<>();
        DFS(root);
        // BFS on graph with target node as center
        List<Integer> ans = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[501];
        visited[target.val] = true;
        q.add(target.val);
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                int node = q.poll();
                if (K == 0) {
                    ans.add(node);
                    continue;
                }
                for (int x : graph[node]) {
                    if (!visited[x]) {
                        q.add(x);
                        visited[x] = true;
                    }
                }
            }
            K--;
            if (K < 0)
                break;
        }
        return ans;
    }

    public void DFS(TreeNode root) {
        if (root == null)
            return;
        if (root.left != null) {
            graph[root.val].add(root.left.val);
            graph[root.left.val].add(root.val);
            DFS(root.left);
        }
        if (root.right != null) {
            graph[root.val].add(root.right.val);
            graph[root.right.val].add(root.val);
            DFS(root.right);
        }
    }
}
```