Quick Overview

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.

Compute time to burn tree

Company: Tesla

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Overview: 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.

Read the full Tesla Backend Engineer interview experience this question came from

You are given a binary tree and the value of a target node that starts burning at time `0`. Every minute, fire spreads from each burning node to its left child, right child, and parent. For this problem, the tree is provided as a level-order list `tree`, where `None` represents a missing node. If a node is stored at index `i`, its left child is at `2*i + 1` and its right child is at `2*i + 2`, as long as those positions exist and are not `None`. Return the number of minutes required for the entire tree to burn. All non-`None` node values are unique. If the tree contains only the target node, the answer is `0`. Example: if the farthest node from the target is 4 edges away, the whole tree burns in 4 minutes.

Constraints

  • `1 <= len(tree) <= 10^5`
  • `tree[0]` is not `None`
  • Each entry in `tree` is either an integer or `None`
  • All non-`None` node values are unique
  • `target` is guaranteed to be one of the non-`None` values in `tree`

Examples

Input: ([1, 2, 3, 4, 5, None, 6], 5)

Expected Output: 4

Explanation: The longest path from node 5 is 5 -> 2 -> 1 -> 3 -> 6, which has 4 edges, so the tree finishes burning in 4 minutes.

Input: ([7], 7)

Expected Output: 0

Explanation: There is only one node, and it is already burning at time 0.

Hints

  1. If you can move from a node to its parent as well as its children, the tree behaves like an undirected graph.
  2. Build the parent/adjacency relationships first, then run BFS from the target one minute at a time to find the farthest reachable node.

Loading coding console...