Python O(n) solution | Simple DFS
Intuition\n> If target found, store childs with distance k and return the distance\n> if current distance if k, store the current node, else store the nodes of 
# Intuition\n> If target found, store childs with distance k and return the distance\n> if current distance if k, store the current node, else store the nodes of remaning distance of other side \n\n# Approach\nDFS\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(log(n))\n\n# Code\n```python3 []\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    """\n    if we find a node, \n    > then we need to start a counter and find the node below it with distance k\n    > HOW do we find the nodes above??\n\n    HOW do we find the nodes above??\n    -what if we return distance of target node in the function.\n    -But suppose the target node is on right and we traversed left part first\n    -In that case, when we find the target node, then we will need to traverse \n    the left part again just to get those node  \n    """\n    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n        out = []\n\n        def find_downwards_dist_nodes(node, dist):\n            if not node:\n                return\n            if dist == 0:\n                out.append(node.val)\n                return \n            find_downwards_dist_nodes(node.left, dist-1)\n            find_downwards_dist_nodes(node.right, dist-1)\n        \n        def helper(curr_node=root):\n            if not curr_node:\n                return -1\n            \n            # if not found, then just take the downwards nodes of distance k and\n            # return distance of 1\n            if curr_node == target:\n                find_downwards_dist_nodes(curr_node, k)\n                return 1\n            \n\n            left_dis = helper(curr_node.left)\n            if left_dis == k: \n                # current distance is k then there can be no other node on right\n                # or above current which have distance of k\n                out.append(curr_node.val)\n                return -1\n            elif left_dis != -1:\n                # check on right for the nodes with remaning distance \n                find_downwards_dist_nodes(curr_node.right, k-left_dis-1)\n                return left_dis + 1\n            \n            right_dis = helper(curr_node.right)\n            if right_dis == k:\n                # current distance is k then there can be no other node on left\n                # or above current which have distance of k\n                out.append(curr_node.val)\n                return -1\n            elif right_dis != -1:\n                # check on left for the nodes with remaning distance \n                find_downwards_dist_nodes(curr_node.left, k-right_dis-1)\n                return right_dis + 1\n            \n            # if no matching node found\n            return -1\n\n        helper()\n        return out\n\n```
['Python3']