InternDoor

How long until the whole tree is infected

Mediumtrees · breadth-first search · graphs

Reported in interviews at (where)

Every value in the binary tree is different. At minute 0 only the node holding start is infected. Each minute, every infected node infects its neighbours: its left child, its right child and its parent.

Return how many minutes pass until every node is infected.

Example 1
Input
root = [7,2,9,4,null,null,1,8]
start = 9
Output
4

Minute 1: 7 and 1. Minute 2: 2. Minute 3: 4. Minute 4: 8, the last one, reached through the root.

Example 2
Input
root = [6]
start = 6
Output
0

The only node is infected at the start.

Limits

  • 1 <= number of nodes <= 20000
  • 1 <= Node.val <= 100000
  • all values are different
  • start is the value of a node in the tree
  • the tree is at most 3000 levels deep

Hints

Hint 1

The infection also moves up to parents, so treat the tree as a graph with edges both ways.

Hint 2

Record each node's parent in one pass, then search breadth-first from the starting node. The answer is the distance to the farthest node.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.