← Tesla Interview Insights

Tesla·Backend Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Tesla backend interview with a tree problem that looks clean on the surface but has a few gotchas worth thinking through. Nothing too wild, but the BFS-from-target angle tripped me up a bit.

Questions Asked (1)

Q1

Given a binary tree and a target node that starts burning at time 0, fire spreads each minute to adjacent nodes (left child, right child, parent). How many minutes does it take for the whole tree to burn?

Algorithms & Data Structures
Author's notes

The spread-to-parent part is what gets you.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tree as an undirected graph and perform a multi-source BFS from the target node, treating each edge as unit weight. The answer is the maximum distance from the target to any node, which can be computed in O(n) time. Alternatively, use a two-pass DFS to compute the farthest distance in each subtree and combine with the distance from the target.

Pro tip: Clarify that the tree is unrooted for the fire spread, so parent edges must be considered. Mention that the solution is O(n) time and O(n) space, and that it can be optimized to O(1) extra space with a DFS that returns the farthest distance in the subtree.

1. Clarify the problem

Confirm that the tree is binary, the target node is given, and fire spreads to all adjacent nodes (left, right, parent) each minute. Ask if the tree is rooted and if parent pointers are available.

2. Model as graph

Treat the tree as an undirected graph where each node is connected to its left child, right child, and parent. This allows fire to spread in all directions.

3. Choose algorithm

Use BFS from the target node to compute the shortest time to reach each node. The answer is the maximum distance. Alternatively, use a two-pass DFS to compute the farthest distance in each subtree and combine with the distance from the target.

4. Implement and analyze

Write code for BFS or DFS, ensuring O(n) time and O(n) space. Explain how to handle parent pointers if not given (e.g., build adjacency list or use recursion with parent parameter).

5. Test and edge cases

Test with target as root, leaf, or internal node. Consider a skewed tree and a balanced tree. Verify the answer for small trees manually.

Key Points to Mention

  • The problem is equivalent to finding the maximum distance from the target node to any other node in the tree.
  • BFS from the target node is a straightforward O(n) solution.
  • A two-pass DFS can compute the answer without explicitly building a graph, using the fact that the farthest node is either in the target's subtree or outside it.
  • The time complexity is O(n) and space complexity is O(n) for BFS, or O(h) for DFS (h = height).
  • Edge cases: target is the only node, target is a leaf, tree is skewed.
  • If parent pointers are not available, we can build an adjacency list or use recursion with a parent parameter to avoid revisiting.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.