Amount of Time for Binary Tree to Be Infected
Asked at Salesforce
Problem
Given the root of a binary tree and an integer start representing the initially infected node, find the time in minutes for the entire tree to be infected. Each minute, an infected node infects its uninfected neighbors (parent and children). This tests your ability to model tree propagation as a graph BFS.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
Brute force: simulate infection level by level. Start from the start node, BFS outward through parent and child connections. Count the minutes (levels) until all nodes are infected. That's O(n).
Key insight: convert the tree into an undirected graph. Each node has edges to its parent and children. Then BFS from the start node to find the maximum distance (in edges) to any node. That distance is the answer.
Why graph BFS works: infection spreads equally in all directions from the start node. BFS naturally explores level by level, so the number of BFS levels equals the number of minutes. The last node infected is the farthest node from start.
Implementation: first DFS to build an adjacency list (parent-child and child-parent edges). Then BFS from start, tracking visited nodes. The BFS depth is the answer. Alternatively, DFS to find the deepest path from start without going back.
Visual walkthrough for tree: 1->2,1->3,2->4,2->5,5->6 start=3:
Graph adjacency: 1:[2,3], 2:[1,4,5], 3:[1], 4:[2], 5:[2,6], 6:[5].
BFS from 3:
Level 0: {3}. Time=0.
Level 1: {1}. Time=1.
Level 2: {2}. Time=2.
Level 3: {4, 5}. Time=3.
Level 4: {6}. Time=4.
All nodes infected. Answer: 4.
Edge cases: single node tree (return 0), start is the root, start is a leaf, tree is a straight line (linked list shape).
Optimal Approach
Step 1: Build an adjacency list by DFS. For each node, add edges to its parent and children.
Step 2: BFS from the start node, tracking visited nodes.
Step 3: Count BFS levels. The number of levels minus 1 is the answer (minutes).
Walkthrough with tree: 1->2,1->3,2->4,2->5,5->6, start=3:
- Build graph: {1:[2,3], 2:[1,4,5], 3:[1], 4:[2], 5:[2,6], 6:[5]}.
- BFS: queue=[3], visited={3}, minutes=0.
- Process 3: neighbors [1]. Queue=[1], visited={3,1}, minutes=1.
- Process 1: neighbors [2,3]. 3 visited. Queue=[2], visited={3,1,2}, minutes=2.
- Process 2: neighbors [1,4,5]. 1 visited. Queue=[4,5], visited={3,1,2,4,5}, minutes=3.
- Process 4: neighbors [2]. Visited. Process 5: neighbors [2,6]. Queue=[6], visited={3,1,2,4,5,6}, minutes=4.
- Process 6: neighbors [5]. Visited. Queue empty. Answer: 4.
Time: O(n) for DFS + BFS. Space: O(n) for adjacency list and queue.
What Trips People Up in Real Interviews
Forgetting that infection can go UP to the parent. This is not just a downward propagation - it spreads in all directions. You must model parent-child relationships as bidirectional edges.
Trying to BFS on the tree directly without building the graph. On a tree, you can only go down. But infection goes up too, so you need the parent connection. Build the adjacency list first.
Returning the BFS level count instead of level count minus 1. The start node is at level 0 (minute 0). The first neighbors are at level 1 (minute 1). So the answer is the max level, not max level + 1.
Not tracking visited nodes. Without a visited set, BFS will oscillate between parent and child infinitely. Always mark nodes as visited when you enqueue them.
Using DFS to find the answer directly without the graph conversion. DFS can work (find two longest paths from start, take the max) but is much harder to reason about. Graph BFS is cleaner and less error-prone.
Solution Code
def amountOfTime(root, start):
adj = {}
def dfs(node, parent):
if not node:
return
if node.val not in adj:
adj[node.val] = []
if parent:
adj[node.val].append(parent.val)
adj[parent.val].append(node.val)
dfs(node.left, node)
dfs(node.right, node)
dfs(root, None)
from collections import deque
queue = deque([start])
visited = {start}
minutes = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
for neighbor in adj.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
minutes += 1
return minutes - 1Frequently Asked Questions
What is the Amount of Time for Binary Tree to Be Infected problem?
Given the root of a binary tree and an integer start representing the initially infected node, find the time in minutes for the entire tree to be infected. Each minute, an infected node infects its uninfected neighbors (parent and children). This tests your ability to model tree propagation as a graph BFS.
How do you solve Amount of Time for Binary Tree to Be Infected?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Amount of Time for Binary Tree to Be Infected?
Amount of Time for Binary Tree to Be Infected is asked at Salesforce. It is a medium difficulty problem.
What are common mistakes on Amount of Time for Binary Tree to Be Infected?
- Forgetting that infection can go UP to the parent. This is not just a downward propagation - it spreads in all directions. You must model parent-child relationships as bidirectional edges.
- Trying to BFS on the tree directly without building the graph. On a tree, you can only go down. But infection goes up too, so you need the parent connection. Build the adjacency list first.
- Returning the BFS level count instead of level count minus 1. The start node is at level 0 (minute 0). The first neighbors are at level 1 (minute 1). So the answer is the max level, not max level + 1.
- Not tracking visited nodes. Without a visited set, BFS will oscillate between parent and child infinitely. Always mark nodes as visited when you enqueue them.
- Using DFS to find the answer directly without the graph conversion. DFS can work (find two longest paths from start, take the max) but is much harder to reason about. Graph BFS is cleaner and less error-prone.