Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Fire spreads one edge per minute in every direction — including up to the parent.
  2. 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