Amount of Time for Binary Tree to Be Infected

Problem Statement:

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start. Each minute, a node becomes infected if:

• The node is currently uninfected.
• The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

Example 1:

Input: root = [1,5,3,null,4,10,6,9,2], start = 3 Output: 4 Explanation: The following nodes are infected during:

• Minute 0: Node 3
• Minute 1: Nodes 1, 10 and 6
• Minute 2: Node 5
• Minute 3: Node 4
• Minute 4: Nodes 9 and 2 It takes 4 minutes for the whole tree to be infected so we return 4.

Solution:

class Solution {
    public int amountOfTime(TreeNode root, int start) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        convertToGraph(root, adjList);
 
        Queue<Integer> q = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        q.add(start);
        int time = -1;
        
        while(!q.isEmpty()){
            int size = q.size();
            //work
            time++;
            
            for(int i = 0; i < size; i++){
                //remove
                int currNode = q.poll();
                //mark*
                visited.add(currNode);
 
                //add*
                if(adjList.containsKey(currNode)){
                    for(Integer nbr: adjList.get(currNode)){
                        if(!visited.contains(nbr)){
                            q.add(nbr);
                        }
                    }
                }
            }
        }
 
        return time;
    }
 
    private void convertToGraph(TreeNode node, Map<Integer, List<Integer>> adjacencyList) {
        if (node == null) {
            return;
        }
      
        if (node.left != null) {
            adjacencyList.computeIfAbsent(node.val, k -> new ArrayList<>()).add(node.left.val);
            adjacencyList.computeIfAbsent(node.left.val, k -> new ArrayList<>()).add(node.val);
        }
      
        if (node.right != null) {
            adjacencyList.computeIfAbsent(node.val, k -> new ArrayList<>()).add(node.right.val);
            adjacencyList.computeIfAbsent(node.right.val, k -> new ArrayList<>()).add(node.val);
        }
      
        
        convertToGraph(node.left, adjacencyList);
        convertToGraph(node.right, adjacencyList);
    }
}