Java - O(1) space excluding recursive stack space
\nThere are problems on LeetCode, \n1. Where we need to propagate a value down the tree from root to child, like in finding the longest path from root to child.
\nThere are problems on LeetCode, \n1. Where we need to propagate a value down the tree from root to child, like in finding the longest path from root to child. \n2. Where we use the returned value from the children, like in lowest common ancestor. \n\nIn this problem, we just need to use both the concepts together.\n1. Intially, we propagate a `val = 0` down the tree until target is found. Once we have the target we start incrementing the val and then propagate, when we have `val = k`, we can add that node to result. \n2. Later, we return `val = 0` from the children if it\'s not the target node and it doesn\'t have the target in the subtree. If we find the target we return `val=1`. when a node receives a returned `val > 0`, it needs to re-propagate the new val to the other subtree and return `val+1`. \n\nA picture worth thousand words, \n\n![image](https://s3-lc-upload.s3.amazonaws.com/users/shreyansh94/image_1530561256.png)\n\nI think the code will be much easier to understand than the theory. \n\n```\nclass Solution {\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> dist = new ArrayList<Integer>(); \n\t\t\t\t// Note : Since target is always in the tree, we can do this.\n        if( K == 0){\n            dist.add(target.val); \n            return dist; \n        }\n        traverse(dist, root, target, K, 0); \n        return dist; \n    }\n    public int traverse(List<Integer> dist, TreeNode root, TreeNode target, int k, int val){\n        if(root == null) \n            return 0; \n\t\t\t\t\t\t// val == k implies that we are at the k-th distant child from the target\n        if(val == k){\n            dist.add(root.val); \n            return 0; \n        }\n        int left = 0, right = 0; \n\t\t\t\t\n\t\t\t\t// either we find the target or we have already found the target propagate val+1\n        if(root.val == target.val || val > 0 ){\n            left = traverse(dist, root.left, target, k, val+1); \n            right = traverse(dist, root.right, target, k, val+1); \n        }\n\t\t\t\t\n\t\t\t\t// else propagate the 0\n        else {\n            left = traverse(dist, root.left, target, k, val); \n            right = traverse(dist, root.right, target, k, val); \n        }\n\t\t\t\t\n\t\t\t\t// If a node receives a k in return it is k-th distant parent from the the target.\n        if(left == k || right == k){\n            dist.add(root.val); \n            return 0; \n        }\n\t\t\t\t\n\t\t\t\t// Target node must return 1 other must return 0 if their subtree doesnt have target.\n        if(root.val == target.val){\n            return 1; \n        }\n\t\t\t\t\n\t\t\t\t// If left or right is greater than 0 that means one of the subtree has the target. Propagate the new value in the other subtree. \n        if(left > 0){\n            traverse(dist, root.right, target, k, left + 1); \n        }\n        if(right > 0){\n            traverse(dist, root.left, target, k, right+1); \n        }\n\t\t\t\t// If the subtree has target, return the distance from target +1 \n        if(left > 0 || right > 0)\n            return left > 0 ? left + 1 : right + 1; \n\t\t\t\t\t\t\n\t\t\t\t// else return 0. \n        return 0; \n    }\n}\n```
[]