How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Tesla.

What role is this question designed for?

This question is commonly asked for Backend Engineer candidates at Tesla during technical interviews.

Compute time to burn tree | Tesla Coding Question

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.

Quick Answer: 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.

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.

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

Expected Output: 2

Explanation: This forms a chain 1 -> 2 -> 3 -> 4. Starting from 3, the farthest node is 1, two edges away.

Input: ([10, 5, 15, 2, 7, 12, 20, None, None, 6, 8], 10)

Expected Output: 3

Explanation: Starting from the root 10, the deepest nodes 6 and 8 are 3 edges away, so the full burn time is 3.

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

Expected Output: 4

Explanation: The farthest node from 5 is 3 along the path 5 -> 4 -> 2 -> 1 -> 3, which takes 4 minutes.

Input: ([0, -2, 5, -3, -1, None, 9], -2)

Expected Output: 3

Explanation: From -2, the farthest node is 9 along the path -2 -> 0 -> 5 -> 9, so the answer is 3.

Hints

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

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.