JAVA STEP BY STEP EXPLAINED SOLUTION🔥🤗
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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(N)\n![Screenshot_20230205_171246.png](https://assets.leetcode.com/users/images/5c0ad053-1277-4845-bddb-508169c4144e_1680701899.9465518.png)\n\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode(int x) { val = x; }\n * }\n */\nclass Solution {\n    \n    public void markParents(TreeNode root,Map<TreeNode,TreeNode> parent_track,TreeNode target){\n\n        // Initialize a queue and add the root to it\n        Queue<TreeNode> q = new LinkedList<>();\n        q.offer(root);\n\n        // Traverse the tree using BFS\n        while(!q.isEmpty()){\n            // Remove the current node from the queue\n            TreeNode cur = q.poll();\n\n            // If the current node has a left child, mark the left child\'s parent as the current node\n            if(cur.left != null){\n                parent_track.put(cur.left,cur);\n                q.offer(cur.left);\n            }\n\n            // If the current node has a right child, mark the right child\'s parent as the current node\n            if(cur.right != null){\n                parent_track.put(cur.right,cur);\n                q.offer(cur.right);\n            }\n        }\n    }\n\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n\n        // Initialize a map to track the parents of each node, and mark the parents using the markParents method\n        Map<TreeNode,TreeNode> parent_track = new HashMap<>();\n        markParents(root,parent_track,root);\n\n        // Initialize a map to track visited nodes, and a queue to perform BFS\n        Map<TreeNode,Boolean> visited = new HashMap<>();\n        Queue<TreeNode> q = new LinkedList<>();\n\n        // Add the target node to the queue and mark it as visited\n        q.offer(target);\n        visited.put(target,true);\n\n        int cur_level = 0;\n\n        // Traverse the tree using BFS\n        while(!q.isEmpty()){\n            int size = q.size();\n\n            // If the current level is equal to the desired distance k, exit the loop\n            if(k == cur_level){\n                break;\n            }\n            cur_level++;\n\n            // Traverse all nodes at the current level\n            for(int i = 0; i < size; i++){\n                // Remove the current node from the queue\n                TreeNode current = q.poll();\n\n                // If the current node has a left child that has not been visited, add it to the queue and mark it as visited\n                if(current.left != null && visited.get(current.left) == null){\n                    q.offer(current.left);\n                    visited.put(current.left,true);\n                }\n\n                // If the current node has a right child that has not been visited, add it to the queue and mark it as visited\n                if(current.right != null && visited.get(current.right) == null){\n                    q.offer(current.right);\n                    visited.put(current.right,true);\n                }\n\n                //this checks in upward direction that is there any noe which is present above the target at k distance\n                // If the current node has a parent that has not been visited, add it to the queue and mark it as visited\n                if(parent_track.get(current) != null && visited.get(parent_track.get(current)) == null){\n                    q.offer(parent_track.get(current));\n                    visited.put(parent_track.get(current),true);\n                }\n            }\n        }\n\n        // Add all remaining nodes in the queue to the result list\n        List<Integer> result = new ArrayList<>();\n        while(!q.isEmpty()){\n            TreeNode current = q.poll();\n            result.add(current.val);\n        }\n    return result;\n    }\n}\n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'Java']