JAVA BFS explained with comments line by line
\nclass Solution {\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> res = new ArrayList<>();\n        Map<Tre
```\nclass Solution {\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> res = new ArrayList<>();\n        Map<TreeNode,TreeNode> parentsMap = new HashMap<>();\n        buildParentMap(root,root,parentsMap);//first root is node and second root is its parent considered\n        Set<TreeNode> visited = new HashSet<>(); //keep track of visited nodes\n        Queue<TreeNode> q = new LinkedList<>();//for BFS\n        q.add(target);  //instead of root here we are adding target as we need to find from that node\n        visited.add(target); //also target node need to be visited first\n        int level = 0; //as we are using level order traversal k == level then we find all the nodes in queue\n        while(q.size()>0){\n            int size = q.size();\n            if(level == K) return buildListFromQueue(q);//elements remaining in queue will be nodes at dist \n            for(int i = 0;i<size;i++){                  //k from target\n                TreeNode t = q.remove();\n                if(t.left != null && !visited.contains(t.left)){\n                    q.add(t.left);\n                    visited.add(t.left);\n                }if(t.right != null && !visited.contains(t.right)){\n                    q.add(t.right);\n                    visited.add(t.right);\n                }\n                TreeNode parent = parentsMap.get(t);\n                if(!visited.contains(parent)){ //if parent is not visited \n                    q.add(parent);//add parent to q\n                    visited.add(parent);   //mark it as visited\n                }\n            }\n            level++; //we check levelwise and each level covers 1 unit distance \n        }\n            return res;\n    }\n    private List<Integer> buildListFromQueue(Queue<TreeNode> q){\n        List<Integer> lst = new ArrayList<>();\n        while(q.size()>0){\n            lst.add(q.remove().val);\n        }\n        return lst;\n    }\n    private void buildParentMap(TreeNode root,TreeNode parent,Map<TreeNode,TreeNode> parentsMap){\n        if(root == null)\n            return;\n        parentsMap.put(root,parent);\n        buildParentMap(root.left,root,parentsMap); //build for left subtree root.left will be child of root\n        buildParentMap(root.right,root,parentsMap);//build for right subtree\n    }\n}\n```
['Breadth-First Search', 'Queue', 'Java']