# All Nodes Distance K in Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/all-nodes-distance-k-in-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Nutanix](https://scaleengineer.com/companies/nutanix), [Samsung](https://scaleengineer.com/companies/samsung), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [DP world](https://scaleengineer.com/companies/dp-world)
---
## Problem
Given the `root` of a binary tree, the value of a target node `target`, and an integer `k`, return _an array of the values of all nodes that have a distance_ `k` _from the target node._

You can return the answer in **any order**.

**Example 1:**

![](https://assets.glich.co/dsa/all-nodes-distance-k-in-binary-tree/image0.png) 

**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.

**Example 2:**

**Input:** root = [1], target = 1, k = 3
**Output:** []

**Constraints:**

* The number of nodes in the tree is in the range `[1, 500]`.
* `0 <= Node.val <= 500`
* All the values `Node.val` are **unique**.
* `target` is the value of one of the nodes in the tree.
* `0 <= k <= 1000`

# Approaches
## Graph Traversal with Parent Pointers
This approach transforms the tree traversal problem into a graph traversal problem. Since a standard binary tree only allows downward traversal (from parent to child), we first need a way to traverse upwards. We can achieve this by creating a mapping from each node to its parent. Once we have this parent mapping, we can treat the tree as an undirected graph and perform a Breadth-First Search (BFS) starting from the `target` node to find all nodes at exactly distance `k`.
**Time:** O(N), where N is the number of nodes in the tree. The `findParents` traversal takes O(N) time. The BFS also visits each node and edge at most once, which takes O(N) time. · **Space:** O(N), where N is the number of nodes in the tree. The `parentMap` can store up to N-1 entries. The `visited` set can store up to N nodes. The `queue` in the worst case (a complete binary tree) can hold up to N/2 nodes. Thus, the space complexity is dominated by these data structures.
**Pros:** Conceptually simple and easy to understand if familiar with graph traversal algorithms like BFS.; Correctly handles all cases by converting the tree into a general graph.
**Cons:** Requires extra space proportional to the number of nodes (O(N)) for the parent map, visited set, and queue, which can be significant for large trees.
### Explanation
The method involves two main phases. First, we traverse the entire tree to build a data structure, typically a `HashMap`, that maps each node to its parent. This allows us to move upwards in the tree, which is not possible by default. During this initial traversal, we can also locate the `target` node. 

Once we have the parent pointers and the target node, we start a Breadth-First Search (BFS) from the `target`. BFS is ideal for finding the shortest path in an unweighted graph, which is what our tree has become. We use a queue to manage the nodes to visit and a set to keep track of visited nodes to prevent cycles (e.g., moving from a child to its parent and back). The BFS proceeds in levels, where each level corresponds to an increase in distance from the `target`. We continue the BFS until we have reached level `k`. All nodes at this level are our answer.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        findParents(root, null, parentMap);

        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        
        queue.offer(target);
        visited.add(target);
        
        int currentDistance = 0;
        
        while (!queue.isEmpty()) {
            if (currentDistance == k) {
                break;
            }
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                
                // Add left child
                if (currentNode.left != null && !visited.contains(currentNode.left)) {
                    queue.offer(currentNode.left);
                    visited.add(currentNode.left);
                }
                
                // Add right child
                if (currentNode.right != null && !visited.contains(currentNode.right)) {
                    queue.offer(currentNode.right);
                    visited.add(currentNode.right);
                }
                
                // Add parent
                TreeNode parent = parentMap.get(currentNode);
                if (parent != null && !visited.contains(parent)) {
                    queue.offer(parent);
                    visited.add(parent);
                }
            }
            currentDistance++;
        }
        
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            result.add(queue.poll().val);
        }
        
        return result;
    }

    private void findParents(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {
        if (node == null) {
            return;
        }
        parentMap.put(node, parent);
        findParents(node.left, node, parentMap);
        findParents(node.right, node, parentMap);
    }
}
```
### Algorithm
*   **Step 1: Annotate Parents & Find Target.**
    1.  Create a `Map<TreeNode, TreeNode> parentMap`.
    2.  Traverse the tree using DFS (or BFS). For each `node`, store its parent in the map: `parentMap.put(node, parent)`.
*   **Step 2: BFS from Target.**
    1.  Initialize a `Queue<TreeNode> queue` and a `Set<TreeNode> visited`.
    2.  Add the `target` node to both the `queue` and the `visited` set.
    3.  Initialize `distance = 0`.
    4.  Loop while the `queue` is not empty:
        a. If `distance == k`, stop the loop. The nodes currently in the queue are part of the answer.
        b. Get the number of nodes at the current level: `levelSize = queue.size()`.
        c. Process all nodes at the current level: For `i` from 0 to `levelSize - 1`:
            i. Dequeue `currentNode`.
            ii. For each neighbor of `currentNode` (left child, right child, and parent from `parentMap`):
                - If the neighbor exists and has not been visited, add it to the `queue` and the `visited` set.
        d. Increment `distance`.
*   **Step 3: Collect Results.**
    1.  After the loop terminates, drain the `queue` and add the value of each node to a result list.
    2.  Return the result list.

## Optimized Recursive DFS
This approach avoids creating any auxiliary graph-like data structures (like a parent map or an adjacency list) and instead uses the call stack of a recursive Depth-First Search (DFS) to implicitly handle the upward traversal from the target node. It finds the nodes at distance `k` in a single pass over the tree.
**Time:** O(N), where N is the number of nodes. Each node is visited a constant number of times. The main `dfs` function and the helper `findSubtreeNodes` together ensure that every node is processed at most twice. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N). However, for a balanced tree, H is O(log N), making this approach significantly more space-efficient.
**Pros:** More space-efficient than the graph-based approach, especially for balanced trees, as its space complexity is tied to the tree's height.; Solves the problem in a single pass without needing to pre-process the tree to build parent pointers or an adjacency list.
**Cons:** The recursive logic can be more complex to reason about compared to the straightforward graph traversal.; In the worst-case (a skewed tree), the space complexity is still O(N) due to the recursion depth.
### Explanation
The core of this method is a recursive function, let's call it `dfs`, that traverses the tree and serves two purposes. First, it searches for the `target` node. Second, it uses its return value to communicate the distance from the current node to the `target` back up the call stack.

When the `dfs` function is at a given `node`:
1.  If `node` is the `target`, it means we've found the starting point. We then trigger a separate downward search (`findSubtreeNodes`) from this `target` node to find all its descendants at distance `k`. The function returns 0 to its parent, indicating the distance.
2.  If `node` is not the `target`, it recursively calls `dfs` on its children. If a recursive call (say, from the left child) returns a non-negative value `d`, it means the `target` is in the left subtree at a distance `d` from the left child. Therefore, the `target` is at distance `d + 1` from the current `node`.
3.  Now, from this current `node`, we know the path to the `target` goes through its left child. We check if the `node` itself is at distance `k`. We also need to find nodes in the *other* subtree (the right one) that are at the required distance. The path to these nodes goes up to the current `node` and then down into the right subtree. We can calculate the remaining distance and call `findSubtreeNodes` on the right child.

This process effectively explores all paths from the target: downwards into its own subtree, and upwards to each ancestor, branching off into the ancestor's other subtrees.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> result;
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        result = new ArrayList<>();
        dfs(root, target, k);
        return result;
    }

    // Returns the distance from node to target.
    // Returns -1 if target is not in the subtree of node.
    private int dfs(TreeNode node, TreeNode target, int k) {
        if (node == null) {
            return -1;
        }

        if (node == target) {
            // Found the target node. Now find all nodes in its subtree at distance k.
            findSubtreeNodes(node, k);
            return 0; // Distance from target to itself is 0.
        }

        // Recurse on left subtree
        int leftDist = dfs(node.left, target, k);
        if (leftDist != -1) {
            // Target is in the left subtree
            int distFromNodeToTarget = leftDist + 1;
            if (distFromNodeToTarget == k) {
                result.add(node.val);
            }
            // Search in the right subtree for nodes at the required distance
            findSubtreeNodes(node.right, k - distFromNodeToTarget - 1);
            return distFromNodeToTarget;
        }

        // Recurse on right subtree
        int rightDist = dfs(node.right, target, k);
        if (rightDist != -1) {
            // Target is in the right subtree
            int distFromNodeToTarget = rightDist + 1;
            if (distFromNodeToTarget == k) {
                result.add(node.val);
            }
            // Search in the left subtree for nodes at the required distance
            findSubtreeNodes(node.left, k - distFromNodeToTarget - 1);
            return distFromNodeToTarget;
        }

        return -1; // Target not found in this subtree
    }

    // Helper to find nodes in the subtree of 'node' at a specific distance 'dist'
    private void findSubtreeNodes(TreeNode node, int dist) {
        if (node == null || dist < 0) {
            return;
        }
        if (dist == 0) {
            result.add(node.val);
            return;
        }
        findSubtreeNodes(node.left, dist - 1);
        findSubtreeNodes(node.right, dist - 1);
    }
}
```
### Algorithm
*   **Step 1: Main Recursive Function `dfs(node, target, k)`**
    1.  **Base Case:** If `node` is null, return -1 (target not found).
    2.  **Target Found:** If `node` is the `target`, we must find all nodes in its own subtree at distance `k`. Call a helper `findSubtreeNodes(node, k)`. Then, return 0 to signal the distance from the target to itself.
    3.  **Recursive Step:** Recursively call `dfs` on the left and right children.
        `leftDist = dfs(node.left, ...)`
        `rightDist = dfs(node.right, ...)`
*   **Step 2: Process Distances and Propagate Upwards**
    1.  **Target in Left Subtree:** If `leftDist` is not -1:
        a. The distance from the current `node` to the `target` is `leftDist + 1`.
        b. If this distance equals `k`, add `node.val` to the results.
        c. Search in the *other* (right) subtree for nodes. The required distance is `k - (leftDist + 1) - 1`. Call `findSubtreeNodes(node.right, k - leftDist - 2)`.
        d. Return `leftDist + 1` to the parent.
    2.  **Target in Right Subtree:** Perform a symmetric operation if `rightDist` is not -1.
    3.  **Target Not Found:** If both `leftDist` and `rightDist` are -1, return -1.
*   **Step 3: Helper `findSubtreeNodes(node, dist)`**
    1.  A simple DFS that collects all nodes at a specific depth `dist` from `node`.
    2.  **Base Case:** If `node` is null or `dist < 0`, return.
    3.  **Distance Match:** If `dist == 0`, add `node.val` to results.
    4.  **Recurse:** Call `findSubtreeNodes` on children with `dist - 1`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private Map < TreeNode , TreeNode > p ; private Set < Integer > vis ; private List < Integer > ans ; public List < Integer > distanceK ( TreeNode root , TreeNode target , int k ) { p = new HashMap <>(); vis = new HashSet <>(); ans = new ArrayList <>(); parents ( root , null ); dfs ( target , k ); return ans ; } private void parents ( TreeNode root , TreeNode prev ) { if ( root == null ) { return ; } p . put ( root , prev ); parents ( root . left , root ); parents ( root . right , root ); } private void dfs ( TreeNode root , int k ) { if ( root == null || vis . contains ( root . val )) { return ; } vis . add ( root . val ); if ( k == 0 ) { ans . add ( root . val ); return ; } dfs ( root . left , k - 1 ); dfs ( root . right , k - 1 ); dfs ( p . get ( root ), k - 1 ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: unordered_map < TreeNode * , TreeNode *> p ; unordered_set < int > vis ; vector < int > ans ; vector < int > distanceK ( TreeNode * root , TreeNode * target , int k ) { parents ( root , nullptr ); dfs ( target , k ); return ans ; } void parents ( TreeNode * root , TreeNode * prev ) { if ( ! root ) return ; p [ root ] = prev ; parents ( root -> left , root ); parents ( root -> right , root ); } void dfs ( TreeNode * root , int k ) { if ( ! root || vis . count ( root -> val )) return ; vis . insert ( root -> val ); if ( k == 0 ) { ans . push_back ( root -> val ); return ; } dfs ( root -> left , k - 1 ); dfs ( root -> right , k - 1 ); dfs ( p [ root ], k - 1 ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def distanceK ( self , root : TreeNode , target : TreeNode , k : int ) -> List [ int ]: def parents ( root , prev ): nonlocal p if root is None : return p [ root ] = prev parents ( root . left , root ) parents ( root . right , root ) def dfs ( root , k ): nonlocal ans , vis if root is None or root . val in vis : return vis . add ( root . val ) if k == 0 : ans . append ( root . val ) return dfs ( root . left , k - 1 ) dfs ( root . right , k - 1 ) dfs ( p [ root ], k - 1 ) p = {} parents ( root , None ) ans = [] vis = set () dfs ( target , k ) return ans
```