Amount of Time for Binary Tree to Be Infected

Amount of Time for Binary Tree to Be Infected

What is this problem about?

The "Amount of Time for Binary Tree to Be Infected interview question" is a graph traversal problem set within a tree. You are given a binary tree and a starting "infected" node. Every minute, the infection spreads to all adjacent nodes (parent and children). You need to find the total number of minutes it takes for the entire tree to be infected. This is essentially finding the maximum distance from the start node to any other node in the tree.

Why is this asked in interviews?

This "Amount of Time for Binary Tree to Be Infected coding problem" is a favorite of Uber, Amazon, and Google. It tests if a candidate can see that a "tree" is just a restricted "graph." It requires converting the tree's parent-child relationships into bidirectional edges and then performing a standard traversal.

Algorithmic pattern used

This problem follows the Graph Conversion and Breadth-First Search (BFS) pattern.

1. Adjacency List: Use DFS to traverse the tree and build a map where each node's value points to a list of its neighbors (children and parent).
2. BFS: Start a BFS from the initial infected node.
3. Level Tracking: Each level of the BFS represents one minute.
4. Visited Set: Keep track of infected nodes to avoid going in circles. The depth of the BFS (number of levels) is the final answer.

Example explanation

Tree: Root 1, Children 2 and 3. Start node: 3.

1. Minutes 0: Node 3 is infected.
2. Minute 1: Infection spreads from 3 to its neighbor, node 1 (parent).
3. Minute 2: Infection spreads from 1 to its other neighbor, node 2 (child). Total Time: 2 minutes.

Common mistakes candidates make

• Only going down: Forgetting that the infection can spread "up" to the parent and then down into other branches.
• Off-by-one: Counting the number of nodes in the BFS path instead of the number of "steps" (minutes).
• Redundant conversion: Trying to do everything in one pass without building the graph first. While possible, it's much harder to implement correctly under interview pressure.

Interview preparation tip

Practice converting trees to graphs. Once a tree is a graph, you can solve many "distance" or "time" problems using a standard BFS. Remember that the "radius" of a graph starting from a node is just the maximum level in a BFS traversal.