Burning Tree

Time: O(n)

Space: O(n)

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?