Amount of Time for Binary Tree to Be Infected

Given the root of a binary tree and the value start of an initially infected node, each minute an infected node spreads the infection to all its adjacent nodes — left child, right child, and parent. Return the number of minutes needed for the entire tree to become infected.

All node values are unique and start exists in the tree. The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The infection spreads to children and the parent, so treat the tree as an undirected graph.

The answer is the distance from start to the farthest node.

Add parent pointers and BFS from start, counting levels — or combine up-distance and down-height in one DFS.

Common doubts

Infection spreads one edge per minute in all directions, so the last node infected is the farthest one, at distance equal to that maximum.

The infection also moves upward to the parent, which a rooted binary tree can't express without recording parents (or handling it in the DFS).

It returns a negative depth for the subtree containing start, so an ancestor can add that distance to the opposite subtree's height.

Interview follow-ups

· What an interviewer asks next.

Both root the tree as a graph and spread from a start node; here you want the maximum distance rather than the nodes at an exact distance.

The eccentricity of the start node — its greatest distance to any other node.

Fun facts

The answer is exactly the start node's eccentricity in the tree viewed as a graph.
The signed-DFS trick — negative depth means 'contains the special node' — recurs in many one-pass tree solutions.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 5, 3, null, 4, 10, 6, 9, 2], start = 3
Output: 4
The infection reaches the farthest nodes (9 and 2) after 4 minutes.

Example 2

Input: root = [1], start = 1
Output: 0
The only node is already infected, so no time is needed.

Constraints

- The number of nodes is in the range [1, 10^5] - 1 <= Node.val <= 10^5 - All Node.val are unique - The start value exists in the tree

The infection spreads to every neighbor — including the parent — so this is graph BFS from start, and the answer is the distance to the farthest node (the last minute someone gets infected). Add parent pointers and BFS outward counting levels, or do a single DFS that, at each node, combines the distance-to-start coming up one side with the height going down the other.

Prerequisites

Before you start

· Concepts used directly in the solution.

Tree as a graph. Each node's neighbors are its two children and its parent.

Eccentricity. The answer is the maximum distance from start to any node.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Spread

“Which nodes get infected each minute?”

Every node adjacent to an infected one — children and parent.

“What's the answer?”

The time the last node is infected, i.e. the farthest distance from start.

The ideal opening — say it like this

Infection spreads to children and parent, so it's BFS from the start node over the tree seen as a graph.

The answer is the distance to the farthest node; I add parent pointers and count BFS levels, or do one DFS combining up-distance and down-height.

Understand the problem

Worked example — tree [1, 5, 3, null, 4, 10, 6, 9, 2], start = 3

from 3 the infection reaches: 10, 6 (down, 1 min); 1 (up, 1 min);
5 (2 min); 4 (3 min); 9, 2 (4 min)
answer: 4

Key observations

1Aha

Spread includes the parent

Upward spread is what makes this more than a downward height computation.

2Aha

Answer = farthest distance from start

The last minute equals the maximum distance from start to any node (its eccentricity).

3Aha

One DFS combines up and down

At an ancestor of start, distance-up plus the opposite subtree's height gives a candidate for the maximum.

Brute force vs optimal

	Parent pointers + BFS	Single signed DFS
Idea	BFS from start; count levels	Combine up-distance and down-height per node
Time	O(n)	O(n)
Space	O(n)	O(height)

Both are O(n); parent-BFS is the most transparent. Full code is in the Approaches selector below.

Summary

Key takeaway

The answer is the farthest distance from start. Add parent pointers and BFS from start counting levels, or do one DFS combining distance-up-to-a-node with the height of its opposite subtree. O(n).

wire parents; BFS from start over {left, right, parent}
minutes = number of BFS levels - 1