coding challenges · high

Burn the Binary Tree from a Target Node

Adobe 'burn the binary tree from a target node'. Fire spreads each second to all adjacent nodes; in a tree those are the two children plus the parent, so the answer is the maximum distance from the target. Since tree nodes only point downward, first BFS (or DFS) once to build a parent map (child→parent) and capture the target node pointer — making the tree an undirected graph. Then BFS outward from the target over {left, right, parent} using a visited set (essential, or BFS bounces between a node and its parent), processing one level per second (snapshot the queue size before the inner loop). The number of levels is the burn time (start the counter at -1 because the target is already burning at second 0). Both passes are O(n) time, O(n) space. Edge cases: root target (downward only), leaf target (climbs up then across), single node (0). Same parent-link BFS pattern as LeetCode 863 (All Nodes Distance K) and 2385 (infection time).

The code

// Burn a binary tree from a target node. Fire spreads to adjacent nodes
// (parent + both children) each second. Return seconds to burn it ALL.
int minTimeToBurn(TreeNode* root, int target) {
    std::unordered_map<TreeNode*, TreeNode*> parent;   // child -> parent
    TreeNode* tgt = nullptr;

    // 1) BFS once to record parents and find the target node.
    std::queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        auto* n = q.front(); q.pop();
        if (n->val == target) tgt = n;
        if (n->left)  { parent[n->left]  = n; q.push(n->left);  }
        if (n->right) { parent[n->right] = n; q.push(n->right); }
    }

    // 2) BFS outward from target over {left, right, parent}; count levels.
    std::unordered_set<TreeNode*> seen{tgt};
    q.push(tgt);
    int time = -1;                       // last level adds no new layer
    while (!q.empty()) {
        int sz = q.size();               // one ring = one second
        ++time;
        for (int i = 0; i < sz; ++i) {
            auto* n = q.front(); q.pop();
            for (TreeNode* nb : {n->left, n->right, parent.count(n)?parent[n]:nullptr})
                if (nb && !seen.count(nb)) { seen.insert(nb); q.push(nb); }
        }
    }
    return time;
}

What this lesson walks through

1. 01Fire spreads to neighbours — children AND parent
2. 02Pass 1 — record parents, find the target
3. 03Pass 2 — BFS outward, one ring per second
4. 04Farthest node burns last → answer = 2
5. 05Complexity & the transferable pattern

Fire starts at the target and each second jumps to every adjacent node. In a tree a node's neighbours are its two children and its parent, so the burn time is the maximum distance from the target.