# 2385. Amount of Time for Binary Tree to Be Infected

``````class Solution {
/** Intuition:
We need to do breadth-first search from the start. For that
1. Need a connection between child and parent nodes
2. Find the start node
*/
HashMap<Integer, TreeNode> parentChildMap = new HashMap<Integer, TreeNode>();
TreeNode startNode = null;
public int amountOfTime(TreeNode root, int start) {
traverseTree(root, start);
parentChildMap.put(root.val, null); // Step 1 and 2 complete

HashSet<Integer> visited = new HashSet<Integer>();
int seconds = -1;
while(queue.size() > 0) {
int size = queue.size();
for(int i=0;i<size;i++) {
TreeNode temp = queue.poll();
if (temp.left != null && !visited.contains(temp.left.val)) {
}

if (temp.right != null && !visited.contains(temp.right.val)) {
}

TreeNode parent = parentChildMap.get(temp.val);

if (parent != null && !visited.contains(parent.val)) {
}
}
seconds++;
}
return seconds;
}

public void traverseTree(TreeNode node, int start) {
if(node == null) {
return;
}
if (start == node.val) {
startNode = node;
}
if (node.left != null) {
parentChildMap.put(node.left.val, node);
}
if (node.right != null) {
parentChildMap.put(node.right.val, node);
}
traverseTree(node.left, start);
traverseTree(node.right, start);
}
}
``````

## Decoding the Algorithm:

### 1. Initialization and Connection Mapping:

• A HashMap (`parentChildMap`) is used to establish connections between child and parent nodes, essential for navigating the tree.
• The `startNode` is identified by traversing the tree until the desired node with the given value (`start`) is found.

• A LinkedList (`queue`) and a HashSet (`visited`) facilitate BFS traversal.
• The algorithm starts BFS from the identified `startNode`.
• Nodes are enqueued and dequeued, and their children and parent nodes are added to the queue for exploration.

### 3. Time Calculation:

• The variable `seconds` keeps track of the number of iterations, representing the time taken to reach the root.
• The algorithm increments `seconds` each time all nodes at the current level are processed.

## Unveiling the Intuition:

The intuition behind this algorithm lies in its threefold approach:

1. Establishing Connections:
• The creation of a map connecting child and parent nodes is crucial for traversing the tree efficiently.
2. Locating the Starting Point:
• Identifying the starting node sets the stage for the traversal, ensuring the journey begins from the right point.
• BFS systematically explores the tree, considering child nodes, parent nodes, and their connections, accumulating the time taken to reach the root.

## Conclusion:

Traversing a tree is akin to navigating a complex network of interconnected nodes. This algorithm elegantly combines connection mapping, node identification, and BFS to calculate the time it takes to traverse from a given node to the root. As we unravel the intricacies of this code, we gain insights into the thoughtful design that powers efficient tree exploration in the world of algorithms.