Most easy and intuitive solution | Beats 97.37% ✨
IntuitionWe need to find all the nodes in a binary tree that are at a distance k from a target node. The challenge here is that the tree only allows moving to c

## Intuition
We need to find all the nodes in a binary tree that are at a distance `k` from a **target node**. The challenge here is that the tree only allows moving to child nodes (left and right), but we also need to move **upward** to the parent node.

---

## Approach

### Step 1: Build Parent Map
- To move **upward** in the tree, we first record each node's **parent** in a `HashMap`.
- This is done using a helper function `buildmap(TreeNode node)`, which recursively maps each child node to its parent.

For example, in this tree:
```
       3
      / \
     5   1
    / \
   6   2
```
The `parentmap` will look like:
```
{ 5 -> 3, 6 -> 5, 2 -> 5, 1 -> 3 }
```

---

### Step 2: DFS from the Target Node
- Start from the **target node** and perform a Depth First Search (DFS).
- Keep track of the current **distance** as you move:
   - **Move to the left child**.
   - **Move to the right child**.
   - **Move to the parent node** (using the `parentmap`).
- Use a **HashSet** (`visited`) to ensure that each node is only processed once and to avoid cycles.

### Step 3: Collect Nodes at Distance `k`
- If the current `distance` equals `k`, add the node’s value to the result list.

---

## Complexity

### Time Complexity:
- **O(N)**, where `N` is the total number of nodes in the tree.
   - Building the parent map requires visiting all nodes once.
   - The DFS to find nodes at distance `k` also visits each node once.

### Space Complexity:
- **O(N)** for the `parentmap` and `visited` set.
- The recursion stack may take up to **O(H)** space, where `H` is the height of the tree.

---
## Complete code:

```java []
class Solution {
    List<Integer> result = new ArrayList<>();
    Map<TreeNode,TreeNode> parentmap = new HashMap<>();
    Set<TreeNode> visited = new HashSet<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        buildmap(root);
        FindTarget(target,0,k);
        return result;
    }

    public void buildmap(TreeNode node){
        if(node.left != null){
            parentmap.put(node.left,node);
            buildmap(node.left);
        }
        if(node.right != null){
            parentmap.put(node.right,node);
            buildmap(node.right);
        }
    }

    public void FindTarget(TreeNode node ,int distance , int k){

       if(node == null || visited.contains(node)){
        return;
       }
       visited.add(node);
       
        if(distance == k){
            result.add(node.val);
            return ;
        }
        if(node.left != null){
            FindTarget(node.left,distance+1,k);
        }
        if(node.right != null){
            FindTarget(node.right,distance+1,k);
        }
        if(parentmap.get(node) != null){
            FindTarget(parentmap.get(node),distance+1,k);
        }
    }
}
```
```C++ []
class Solution {
public:
    vector<int> result;
    unordered_map<TreeNode*, TreeNode*> parentMap;
    unordered_set<TreeNode*> visited;

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        buildMap(root);
        findTarget(target, 0, k);
        return result;
    }

    void buildMap(TreeNode* node) {
        if (node->left != nullptr) {
            parentMap[node->left] = node;
            buildMap(node->left);
        }
        if (node->right != nullptr) {
            parentMap[node->right] = node;
            buildMap(node->right);
        }
    }

    void findTarget(TreeNode* node, int distance, int k) {
        if (node == nullptr || visited.count(node)) {
            return;
        }
        visited.insert(node);

        if (distance == k) {
            result.push_back(node->val);
            return;
        }
        if (node->left != nullptr) {
            findTarget(node->left, distance + 1, k);
        }
        if (node->right != nullptr) {
            findTarget(node->right, distance + 1, k);
        }
        if (parentMap.count(node)) {
            findTarget(parentMap[node], distance + 1, k);
        }
    }
};
```



## Code Walkthrough

Here’s a breakdown of the code:

1. **Parent Map Creation**:
   ```java
   public void buildmap(TreeNode node){
       if(node.left != null){
           parentmap.put(node.left, node);
           buildmap(node.left);
       }
       if(node.right != null){
           parentmap.put(node.right, node);
           buildmap(node.right);
       }
   }
   ```
   - This records the parent of every node.

2. **DFS from Target**:
   ```java
   public void FindTarget(TreeNode node, int distance, int k){
       if(node == null || visited.contains(node)) return;

       visited.add(node); // Mark node as visited
       
       if(distance == k){
           result.add(node.val); // Add to result if distance == k
           return;
       }

       // Explore left, right and parent nodes
       FindTarget(node.left, distance + 1, k);
       FindTarget(node.right, distance + 1, k);
       FindTarget(parentmap.get(node), distance + 1, k);
   }
   ```

3. **Driver Method**:
   ```java
   public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
       buildmap(root); // Build parent map
       FindTarget(target, 0, k); // Start DFS from target
       return result; // Return result
   }
   ```

---

## How It Works ?

For this tree:
```
       3
      / \
     5   1
    / \
   6   2
      / \
     7   4
```
If the **target = 5** and **k = 2**:
1. Build parent map.
2. Start DFS from node `5`.
3. At `distance = 2`, collect nodes `7`, `4`, and `3`.

**Output**: `[7, 4, 3]`.

---

### Why Use `visited`?
Without `visited`, the DFS might revisit nodes (e.g., parent → child → parent), causing an infinite loop.

Thank You !!
['Hash Table', 'Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'C++', 'Java']