Practice › Trees
Time to Burn a Binary Tree
Hard · Trees · Asked at Amazon, Microsoft, Flipkart
A fire starts at the node with value target. Every minute it spreads from each burning node to its parent and children. Print the number of minutes until the whole tree is burning. All values are distinct.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node. Third line: target.
Output
The number of minutes.
Constraints
- 1 ≤ number of nodes ≤ 10^4
- target is in the tree
It is the largest distance from the target to any node: BFS from the target over children and parent links.
Example 1
Input
11 1 2 3 4 5 -1 6 -1 -1 7 8 8
Output
5
Example 2
Input
1 1 1
Output
0
Hints
- Fire spreads one edge per minute in every direction — including up to the parent.
- So the answer is the largest distance from the target to any node. Record parents, then BFS from the target and count the layers.
Approach
Record each node's parent while locating the target. Run BFS from the target over left, right and parent with a visited set; every BFS layer is one minute. The number of layers after the first is the time when the last node catches fire.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
int main() {
Node *root = readTree();
long long target;
cin >> target;
unordered_map<Node *, Node *> parent;
Node *start = nullptr;
queue<Node *> q;
q.push(root);
while (!q.empty()) {
Node *n = q.front();
q.pop();
if (n->val == target) start = n;
for (Node *c : {n->left, n->right})
if (c) parent[c] = n, q.push(c);
}
unordered_set<Node *> seen = {start};
vector<Node *> layer = {start};
int minutes = -1;
while (!layer.empty()) {
minutes++;
vector<Node *> next;
for (Node *n : layer)
for (Node *m : {n->left, n->right, parent.count(n) ? parent[n] : nullptr})
if (m && !seen.count(m)) seen.insert(m), next.push_back(m);
layer = next;
}
cout << minutes << "\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
target = rest[0]
parent, start, q = {root: None}, None, deque([root])
while q:
n = q.popleft()
if n.val == target:
start = n
for c in (n.left, n.right):
if c:
parent[c] = n
q.append(c)
seen, layer, minutes = {start}, [start], -1
while layer:
minutes += 1
nxt = []
for n in layer:
for m in (n.left, n.right, parent[n]):
if m and m not in seen:
seen.add(m)
nxt.append(m)
layer = nxt
print(minutes)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node root = readTree(sc);
long target = sc.nextLong();
Map<Node, Node> parent = new HashMap<>();
Node start = null;
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
if (n.val == target) start = n;
if (n.left != null) { parent.put(n.left, n); q.add(n.left); }
if (n.right != null) { parent.put(n.right, n); q.add(n.right); }
}
Set<Node> seen = new HashSet<>(List.of(start));
List<Node> layer = new ArrayList<>(List.of(start));
int minutes = -1;
while (!layer.isEmpty()) {
minutes++;
List<Node> next = new ArrayList<>();
for (Node n : layer)
for (Node m : new Node[] {n.left, n.right, parent.get(n)})
if (m != null && seen.add(m)) next.add(m);
layer = next;
}
System.out.println(minutes);
}
}Solve Time to Burn a Binary Tree online · All practice problems