Katkat
Back

Compute time to burn tree

TeslaBackend Engineer · Onsite
MediumBackend EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates proficiency with tree algorithms, distance computation, and propagation modeling, testing the ability to reason about how a process spreads across parent-child relationships in a tree.

Given the root of a binary tree and the value of a target node that starts burning at time 0, fire spreads every minute from a burning node to its left child, right child, and parent.

Return the number of minutes required for the entire tree to burn.

Notes:

  • All node values are unique.
  • The tree is not necessarily balanced.
  • If the tree has only the target node, the answer is 0.

Example idea: if the farthest node from the target is 4 edges away, the tree burns completely in 4 minutes.