PPractick

The problem

A fire starts at one node of a binary tree, and every second it spreads from each burning node to its parent and both children. How many seconds until the whole tree is burning? That's the largest distance from the start node to any other node, since fire travels along every edge at the same speed. Record parent pointers, then BFS from the start node counting levels until every node has been reached.

Example: tree [1, 2, 3, 4, 5, 6, 7], fire starts at 2 → 3 seconds (the last nodes to burn are 6 and 7).

Function signature

int minTimeToBurn(TreeNode* root, TreeNode* start);

Test cases

Input (tree, start)	Output	Explanation
([1,2,3,4,5,null,6,null,null,7,8,null,9,null,null,null,null,null,10], 8)	7	8-5-2-1-3-6-9-10
([1, 2, 3, 4, 5, 6, 7], 2)	3	2-1-3-6
([1, 2, 3, 4, 5, 6, 7], 1)	2	From the root: its height
([1, 2, null, 3, null, 4], 3)	2	Up to 1 takes 2 seconds, down to 4 takes 1
([1], 1)	0

(Confirm: fire spreads to the parent and children each second; values are unique; the start node is in the tree.)

How interviewers phrase it

• "Given a binary tree and a target node, find the minimum time required to burn the complete tree if the target is set on fire; fire spreads to adjacent nodes in one second" (GeeksforGeeks "Burning Tree"; LeetCode 2385 "Amount of Time for Binary Tree to Be Infected").

Clarifying questions to ask

1. Does fire spread to the parent as well as the children? (Yes.)
2. Do all edges take exactly one second? (Yes.)
3. Is the start node given as a value or a pointer? (A value is fine when values are unique.)

Follow-ups to expect

1. "Why is the answer a maximum distance?"
2. "Why is BFS natural?"
3. "One-pass DFS alternative?"
4. "How is this related to all nodes at distance K?"
5. "Complexity?"

Related questions

• Print all nodes at a distance of K in BT Hard
• Vertical Order Traversal Medium
• Right/Left View of Binary Tree Medium
• LCA in BT Hard
• Preorder Traversal Easy
• Inorder Traversal of Binary Tree Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in