Burning Tree

Time: O(n)

Space: O(n)

Problem Overview

Fire spreads from target node to all adjacent nodes (parent, children).

Intuition

Fire spreads from target node to all adjacent nodes (parent, children). Model as BFS from the target node treating the tree as a graph. First, find target and track parent pointers.

Algorithm

1DFS to find target node and build parent map.
2BFS from target node: spread to left child, right child, and parent each step.
3Count BFS levels (time steps) until all nodes are burned.

Example Walkthrough

Input: root=[1,2,3,4,5], target=2

1. t=0: burn node 2.
2. t=1: burn 1(parent),4,5(children).
3. t=2: burn 3(sibling via parent 1).
4. Total=2.

Output: 2

Common Pitfalls

• Must track parent pointers since BFS needs to go upward too. Mark visited nodes to avoid cycles.

Burning Tree.java

Java

// Approach: BFS from the target node treating the tree as an undirected graph.
// Build parent pointers first, then multi-source BFS tracking time steps.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    public static int minTime(Node root, int target) {
        Map<Node, Node> parentMap = new HashMap<>();
        // Find the target node and build the parent map
        Node targetNode = BuildParentMap(root, target, parentMap);

        if (targetNode == null)
            return 0; // Target not found in the tree

        // BFS to simulate the burning process
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        queue.add(targetNode);
        visited.add(targetNode);
        int time = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();

                // Check and add the left child
                if (current.left != null && !visited.contains(current.left)) {
                    visited.add(current.left);
                    queue.add(current.left);
                }

                // Check and add the right child
                if (current.right != null && !visited.contains(current.right)) {
                    visited.add(current.right);
                    queue.add(current.right);
                }

                // Check and add the parent
                Node parent = parentMap.get(current);
                if (parent != null && !visited.contains(parent)) {
                    visited.add(parent);
                    queue.add(parent);
                }
            }
            time++; // Increment time after processing all nodes at the current level
        }

        return time - 1; // Subtract 1 because we increment time after the last burn
    }

    private static Node BuildParentMap(Node root, int target, Map<Node, Node> parentMap) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        Node targetNode = null;

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            // If we find the target node, store it
            if (current.data == target)
                targetNode = current;

            // Add left child and set parent
            if (current.left != null) {
                parentMap.put(current.left, current);
                queue.add(current.left);
            }

            // Add right child and set parent
            if (current.right != null) {
                parentMap.put(current.right, current);
                queue.add(current.right);
            }
        }

        return targetNode;
    }
}

Was this solution helpful?