Just One DFS | Short Intuitive Approach | Images | O(N) 🔥
IntuitionThe idea is simple that we do the DFS. But, while doing DFS we will increase the distance from the target node by one on each step. Once we have seen t
## Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

The idea is simple that we do the DFS. But, while doing DFS we will increase the distance from the target node by one on each step. Once we have seen the target node.

![All nodes at distance K](https://assets.leetcode.com/users/images/60e48411-31ee-4654-ab6e-9310a5c477a6_1739759801.0226548.png)



There are multiple such problems in DFS to find out the distances from target node. Let's discuss one by one:

### Problem 1: How to mark nodes already traversed before visiting target node?

You will be thinking that In DFS We will once traverse the left subtree and then what if the target node was in the right subtree. We won't be marking the left subtree nodes. To cover that after Right subtree traversal we will check if the distance of the current node is reduced or not if so Traverse the left subtree once again and find nodes at distance K.

### Problem 2: How to cover the root nodes at distance K?

This is actually simple after the complete traversal of the left and right subtree we can check if the current node distance is K from target if so include this node in to the result.

### Problem 3: What's the job of traversal when we haven't discovered the target node?

At that point we will just try to find for the target node and once we find it we will start pushing the results.

## Approach

- Start the traversal of the tree from the `root` node with the distance from target node marked as `inf`
- Traverse the Left and right subtrees of the root node.
- If At any point we see that current `root` node is the `target` node update the distance to be `0` and traverse the children trees by increasing the distance by 1.
- Also, Update the distance of the current node as minimum of the distance received from the children. 
- Also, Check if the Right subtree resulted in the update in the distance from the target node. Then, Traverse the left subtree again.


```python3 []
class Solution:

    def traverse_and_mark(self, root, dist):
        ans, tar, k = self.ans, self.tar, self.k 
        if not root:
            return dist+1
        if root == tar:
            dist = 0
        
        dist = min(dist, self.traverse_and_mark(root.left, dist+1))
        prev_dist = dist
        dist = min(dist, self.traverse_and_mark(root.right, dist+1))
        if prev_dist != dist:
            self.traverse_and_mark(root.left, dist+1)
        if dist == k:
            ans.append(root.val)
        
        return dist+1

    def distanceK(self, root: TreeNode, tar: TreeNode, k: int) -> List[int]:
        self.ans, self.tar, self.k = [], tar, k
        self.traverse_and_mark(root, dist=float('inf'))
        return self.ans
```

<b>Time Complexity:</b> O(N), where N is the number of nodes.

<b>Space Complexity:</b> O(H), where H is the height of the tree.
['Python3']