Java🔥O(1) Space + Explanation✅ Node to root path Approach🔥98% faster
Intuition\n Describe your first thoughts on how to solve this problem. \nOne of the basic approach is to find NodeToRoot Path but that will be not considered a 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nOne of the basic approach is to find NodeToRoot Path but that will be not considered a good soln due to space complexity of O(n). So better approach is to take advantage of node to root path approach.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nApproach behind this code is that to call our printKdown function at the moment we encounter our target node, After calling printKdown and sending our block Node to be null, we will get all nodes below the target node at a distance of k, we are returning 1 from that if condn because we need to tell our parent that you are at a distance of 1.\nAfter that our left or right call will get get the ans with 1, so if we are getting our ans as a parent from our left child, so we need to now block our left child and depth will be k-left, that is for first parent (k-1), as 1 is returned from that if where node is equal to target so in our printKDown we will return back from our left side due to blocked node condn and then go to other side and get all nodes that are at a distance of k-1 from the parent of target node, and then we are returning left+1 or right+1 so that our grandparent can know that we are at distance of 2 from the target node and the process continues.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(1)\n\n```java []\n//without using extra space\nclass Solution {\n    void printKdown(TreeNode root,int depth,TreeNode block,List<Integer> ans){\n        if(root==null || depth<0 || root==block){\n            return;\n        }\n        if(depth==0){\n            ans.add(root.val);\n            return;\n        }\n        printKdown(root.left,depth-1,block,ans);\n        printKdown(root.right,depth-1,block,ans);\n    }\n    int getNodetoRootPath(TreeNode root,TreeNode target,int k,List<Integer> ans){\n        if(root==null){\n            return -1;\n        }\n        if(root==target){\n           printKdown(root,k,null,ans);\n           return 1;\n        }\n       int left = getNodetoRootPath(root.left,target,k,ans);\n        if(left>0){\n            printKdown(root,k-left,root.left,ans);\n            return left+1;\n        }\n        int right = getNodetoRootPath(root.right,target,k,ans);\n        if(right>0){\n            printKdown(root,k-right,root.right,ans);\n            return right+1;\n        } \n        return -1;\n    }\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        List<Integer> ans = new ArrayList<>();\n        getNodetoRootPath(root,target,k,ans);\n        return ans;\n    }\n}\n```\n``` java []\n//using extra space to get node to root path space-O(n)\nclass Solution {\n    void printKdown(TreeNode root,int depth,TreeNode block,List<Integer> ans){\n        if(root==null || depth<0 || root==block){\n            return;\n        }\n        if(depth==0){\n            ans.add(root.val);\n            return;\n        }\n        printKdown(root.left,depth-1,block,ans);\n        printKdown(root.right,depth-1,block,ans);\n    }\n    ArrayList<TreeNode> getNodetoRootPath(TreeNode root,TreeNode target){\n        if(root==null){\n            return new ArrayList<>();\n        }\n        if(root==target){\n            ArrayList<TreeNode> base = new ArrayList<>();\n            base.add(root);\n            return base;\n        }\n        ArrayList<TreeNode> left = getNodetoRootPath(root.left,target);\n        if(left.size()>0){\n            left.add(root);\n            return left;\n        } \n        ArrayList<TreeNode> right = getNodetoRootPath(root.right,target);\n        if(right.size()>0){\n            right.add(root);\n            return right;\n        } \n        return new ArrayList<>();\n    }\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        ArrayList<TreeNode> n2r = getNodetoRootPath(root,target);\n        int len = n2r.size();\n        TreeNode block = null;\n        List<Integer> ans = new ArrayList<>();\n        for(int i=0;i<len;i++){\n            printKdown(n2r.get(i),k-i,block,ans);\n            block=n2r.get(i);\n        }\n        return ans;\n    }\n}\n```\n\n\n\n\n\n\n![please upvote me.jpg](https://assets.leetcode.com/users/images/0ce66916-cbce-4f58-9e4a-5a20bf322c0d_1689060517.7262146.jpeg)
['Depth-First Search', 'Binary Tree', 'Java']