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:
- Establishing Connections:
- The creation of a map connecting child and parent nodes is crucial for traversing the tree efficiently.
- Locating the Starting Point:
- Identifying the starting node sets the stage for the traversal, ensuring the journey begins from the right point.
- 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.