Solution without new graph/tree or editing the tree
Intuition\nWhen I saw this daily problem, I (being lazy) solved it by building a graph for easy traversal and then bfs. Then I went to the editorial to see the 
# Intuition\nWhen I saw this daily problem, I (being lazy) solved it by building a graph for easy traversal and then bfs. Then I went to the editorial to see the actual solution and was surprised that this was the expected solution.\n\nIt\'s my understanding that creating new structures for tree and list problems:\n1) Sometimes makes it easier\n2) Sometimes makes it trivial\n\nAnd thus the interviewer can very likely say something like "good, but can you do it without creating additional data structures, just traverse the tree/list as it is please?"\nAnd thus I wanted to do just that.\n\n# Approach\nSo if we are currently at the target node, it is easy to find nodes below it (in left and right subtrees) that are k distance from us. The hard part is to get what we have possibly missed above us.\n\nThe key is to get the distance (going down, as we cannot go up) from current node to the target node. If we have that distance, then the distance (d) for the parent of current node is d + 1. We can easily get this recursively. And if we can\'t find target node going down from the current node, we say it\'s -inf.\n\nNow, starting with the root, for each current node we can have 3 situatins:\n1) It itself is the target node. In this case we simply search below it. And return distance to it, which is 0.\n2) Neither left nor right subtree contains target node. We return -inf.\n3) Left **OR** right subtree has target node in it. It can\'t be in both. We know if the target exist below the node by the distance the function returns. Let\'s say it\'s in left and the dist is d. If d + 1 = k, current node is added to the result list.\nIn this case we must search for nodes in right subtree while we can, nodes in the left will be caught naturally as we go down the line. So if the right subtree exists, we initiate search below in it, with distance **k - d - 2**. d because it\'s the distance to "return up" from the target to the left child of the current node (we assume the target was found in the left subtree for this example), and -2 comes from the fact that we go up from that child to the current node, and then go to the right subtree.\n \n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, x):\n#         self.val = x\n#         self.left = None\n#         self.right = None\n\nclass Solution:\n    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n\n        target = target.val\n\n        res = []\n        \n        \'\'\'\n        Visits node and its descendants until depth is reached,\n        appends found values to res\n        \'\'\'\n        def visit_below(node, depth):\n            if depth == 0:\n                res.append(node.val)\n                return\n            if node.left:\n                visit_below(node.left, depth - 1)\n            if node.right:\n                visit_below(node.right, depth - 1)\n\n        \'\'\'\n         - Returns distance from current node to target node if target node is below current node,\n        otherwise returns -inf\n\n         - If current node is target node, initiates search below for nodes with distance k from it\n\n         - If target node exists on either side of the current node \n         (distance to target from one of the children of current node is not -inf), \n         initiates search below on other side with distance changed to (k - distance for the child - 2). \n         -2 comes from the fact that first we\'re looking for the distance for a child, not the node itself, \n         and then looking for nodes in another child\'s subtree  \n        \'\'\'\n        def dist_going_down(node):\n            if not node:\n                return -float(\'inf\')\n            if node.val == target:\n                visit_below(node, k)\n                return 0\n            if not node.left and not node.right:\n                return -float(\'inf\')\n            \n            l, r = dist_going_down(node.left), dist_going_down(node.right)\n            \n            # target node is in the left child\'s subtree\n            if l >= 0:\n                if l + 1 == k:\n                    # current node itself has the right distance\n                    res.append(node.val)\n                if node.right and k - l - 2 >= 0:\n                    # search for nodes in the right child\'s subtree\n                    visit_below(node.right, k - l - 2)\n\n            # target node is in the right child\'s subtree\n            if r >= 0:\n                if r + 1== k:\n                    # current node itself has the right distance\n                    res.append(node.val)\n                if node.left and k - r - 2 >= 0:\n                    # search for nodes in the left child\'s subtree\n                    visit_below(node.left, k - r - 2)\n\n            # if target is found in left or right child\'s subtree, return distance to it from current node, otherwise -inf\n            return 1 + max(l, r)\n        \n        dist_going_down(root)\n        \n        return res\n```
['Depth-First Search', 'Python3']