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
        3. Start doing breadth-first search
     */
    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

        // Step 3. Breadth-First Search
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        HashSet<Integer> visited = new HashSet<Integer>();
        queue.add(startNode);
        visited.add(startNode.val);
        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)) {
                    visited.add(temp.left.val);
                    queue.add(temp.left);
                }

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

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

                if (parent != null && !visited.contains(parent.val)) {
                    visited.add(parent.val);
                    queue.add(parent);
                }
            }
            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);
    }
}

Problem Statement: https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/description/

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.

2. Breadth-First Search (BFS):

• 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.
3. Breadth-First Exploration:
   • 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.