Recursion - time: O(N) | memory: O(N)
The solution becomes simple if you visualize the problem correctly. Consider two trees, both have the same target - 17(purple node) , but different K values (fo
The solution becomes simple if you visualize the problem correctly. Consider two trees, both have the same ***target*** - 17(purple node) , but different ***K*** values (for the first K = 2, for the second K = 3). The nodes we are interested in are indicated in **green**.\n\n![image](https://assets.leetcode.com/users/images/d4522f3f-655e-446e-85e4-e18309ee5a6c_1616659784.4647496.jpeg)\n\n#### **Recursion:**\nLet\'s start with a simple subtask:  *we have found a **subtree where the target is the root node**, and we need to find nodes at a distance K from it.*\n\n![image](https://assets.leetcode.com/users/images/b49977c8-afe9-40c7-8ee6-500220417e92_1616665773.1200135.jpeg)\n\n\nThe solution to this subproblem will be any type of DFS tree traversal - let\'s say it will be a pre-order DFS. All that remains to be done is to decrease the K value as you move away from our *target*. When **K > 0**, this means that we need to go down to the subtrees of the current node, while decreasing K by 1. If **K == 0**, then we have reached the node of interest to us. And the cases when **K < 0** are simply not of interest to us.\n\nNow let\'s move on to the task a little more difficult:  *defining **other nodes** at distance K in **other subtrees***. \nAs you can see from the picture, all we need is to be able to transfer the distance to the nodes located **above** the *target*. We will use recursion - starting from the root, we will recursively call a function that returns the **distance** to the *target*, and if the *target* is not found in some subtree, it returns **0**. \n\nLet\'s refer to the picture. We start from root. There is no *target* in the **left subtree**, so a recursive traversal along the left subtree will return 0. We recursively traverse the **right subtree**. It can be seen that for a node with a value of 23, the **left subtree** contains a *target*, which means that a value non-zero (in this case, 1) will be returned, and we will not find the target in the **right subtree** - and we will get 0. \n\nAs you already understood, we can only have **two return values**: some subtree contains the *target*, which means that we will get **non-zero**, and the other subtree does not contain the *target* - so we will get **zero**. Now let\'s take a closer look at the non-zero return value - what does this mean for a node with a value of 23? This means that we can take this particular node as a "*target*" and decrease K by the obtained distance.\n\nWe were already in the left subtree, and got a distance equal to 1, in the right subtree we were also, and got 0. But since K - distance > 0, we can traverse the right subtree again, thereby returning to the first subproblem (23 - root, 1- distance at which we are looking for nodes from the root).\n\nAt the given moment, our list will contain the following values (with K = 2): **13, 16, 41**\n\nWe repeat similar actions for the node with the value 11. Since the recursive call for the right subtree returned a distance equal to 2, the current node is also added to the answer (since K - distance = 0). (We didnt traverse the left subtree because the distance will be greater than the required one). \n\nAnd our list will contain the following final values (with K = 2): **13, 16, 41, 11**\n\n\n```\nclass Solution {\npublic:\n    std::vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {\n        std::vector<int> res;\n\n        distanceK(root, target, K, res);\n\n        return res;\n    }\n\nprivate:\n    int distanceK(TreeNode* node, TreeNode* target, int K, std::vector<int>& res) {\n        if (node == nullptr) {\n            return 0;\n        }\n        if (node == target) {  // found the target for the current subtree\n            traverseSubtree(node, K, res);\n            return 1;\n        }\n        int distLeft = distanceK(node->left, target, K, res); // distance to target in the left subtree\n\t\t\n        if (distLeft != 0) {\n            if (distLeft == K) {\n                res.push_back(node->val);\n            } else if (distLeft < K) {\n                traverseSubtree(node->right, K - distLeft - 1, res); // visit the right subtree looking for nodes at a given distance\n            }\n            return distLeft + 1; //  return distance to target + 1\n        }   \n        int distRight = distanceK(node->right, target, K, res); // distance to target in the right subtree\n\t\t\n        if (distRight != 0) {\n            if (distRight == K) {\n                res.push_back(node->val);\n            } else if (distRight < K) {\n                traverseSubtree(node->left, K - distRight - 1, res);  // visit the left subtree looking for nodes at a given distance\n            }\n            return distRight + 1; //  return distance to target + 1\n        }\n        return 0; // if reached this place, then there is no target in the current subtree\n    }\n\n    void traverseSubtree(TreeNode* node, int K, std::vector<int>& res) {\n        if (node == nullptr) {\n            return;\n        }\n        if (K == 0) { // found a node at a given distance\n            res.push_back(node->val);\n            return;\n        }\n\t\ttraverseSubtree(node->left,  K - 1, res);  // go down until we find a node at a distance of K \n        traverseSubtree(node->right, K - 1, res);  // (if the depth of the subtree allows us to do this)\n    }\n};\n```\n\n(In the future I will add other solutions)
['Depth-First Search', 'Recursion', 'C', 'C++']