Problem Statement

Given a target node data and a root of binary tree. If the target is set on fire, determine the shortest amount of time needed to burn the entire binary tree.

It is known that in 1 second all nodes connected to a given node get burned. That is its left child, right child, and parent.

Examples

Example 1:

Input: target node = 5
        1
       / \
      2   3
     / \
    4   5
Output: 4

Explanation:
At time t = 0: Node 5 is burning
At time t = 1: Node 2 burns (parent of 5)
At time t = 2: Nodes 1 and 4 burn (parent and child of 2)
At time t = 3: Node 3 burns (child of 1)
The entire tree burns in 4 seconds.

Example 2:

Input: target node = 4
        1
       / \
      2   3
         /
        4
Output: 3

Explanation:
At t = 0: Node 4 is burning.
At t = 1: Node 3 burns (parent of 4).
At t = 2: Node 1 burns (parent of 3).
At t = 3: Node 2 burns (child of 1).
The entire tree burns in 3 seconds.

Example 3:

Input: target node = 1
        1
Output: 0

Explanation: The tree contains only one node, which burns immediately at t = 0

Different Approaches

1️⃣ 

Intuition:

To determine how long it will take for a fire to completely burn a binary tree starting from a specific node, the problem can be effectively solved using a breadth-first search (BFS) approach. The essence of the problem is to simulate the spreading of the fire level by level, considering that the fire can propagate to a node’s left child, right child, and parent. Therefore, it is crucial to maintain a record of each node’s parent to allow traversal up the tree when necessary. By calculating the maximum distance from the starting node to the furthest node affected by the fire, we can determine the total time required for the entire tree to be consumed by the fire.

Approach:

1. Start by using BFS to establish a map where each node is associated with its parent. This mapping helps in tracking the parent of each node, facilitating upward traversal during the fire spread simulation.
2. Locate the node where the fire begins. This node will serve as the starting point for the BFS that simulates the spread of the fire through the tree.
3. Initiate another BFS from the starting node to model how the fire spreads through the tree. During this traversal, consider all possible directions: left, right, and upward, ensuring that each node is only processed once.
4. Keep track of the nodes that have already been visited to avoid redundant processing and to ensure that the BFS traversal is efficient.
5. Measure the farthest distance reached during the BFS to determine the total time needed for the fire to consume the entire tree. This distance, in terms of BFS levels, represents the time required for complete combustion.

Code:

#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int timeToBurnTree(TreeNode* root, int start) {
        if (root == nullptr) {
            return 0;
        }

        // Step 1: Create parent map
        unordered_map<TreeNode*, TreeNode*> parentMap;
        mapParents(root, parentMap);

        // Step 2: Locate the starting node
        TreeNode* startingNode = findNode(root, start);
        if (startingNode == nullptr) {
            return 0; // Starting node not found
        }

        // Step 3: Perform BFS to simulate burning
        queue<TreeNode*> que;
        unordered_set<TreeNode*> visited;
        que.push(startingNode);
        visited.insert(startingNode);

        int timeTaken = 0;
        while (!que.empty()) {
            int levelSize = que.size();
            bool burnedThisLevel = false;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* currentNode = que.front();
                que.pop();

                // Explore left child
                if (currentNode->left && visited.find(currentNode->left) == visited.end()) {
                    que.push(currentNode->left);
                    visited.insert(currentNode->left);
                    burnedThisLevel = true;
                }

                // Explore right child
                if (currentNode->right && visited.find(currentNode->right) == visited.end()) {
                    que.push(currentNode->right);
                    visited.insert(currentNode->right);
                    burnedThisLevel = true;
                }

                // Explore parent
                if (parentMap[currentNode] && visited.find(parentMap[currentNode]) == visited.end()) {
                    que.push(parentMap[currentNode]);
                    visited.insert(parentMap[currentNode]);
                    burnedThisLevel = true;
                }
            }

            // Increment time only if nodes burned at this level
            if (burnedThisLevel) {
                timeTaken++;
            }
        }

        return timeTaken;
    }

private:
    // Helper function to create a parent map
    void mapParents(TreeNode* node, unordered_map<TreeNode*, TreeNode*>& parentMap) {
        queue<TreeNode*> que;
        que.push(node);

        while (!que.empty()) {
            TreeNode* currentNode = que.front();
            que.pop();

            if (currentNode->left) {
                parentMap[currentNode->left] = currentNode;
                que.push(currentNode->left);
            }
            if (currentNode->right) {
                parentMap[currentNode->right] = currentNode;
                que.push(currentNode->right);
            }
        }
    }

    // Helper function to find the node with the target value
    TreeNode* findNode(TreeNode* root, int target) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->data == target) {
            return root;
        }
        TreeNode* leftResult = findNode(root->left, target);
        if (leftResult) {
            return leftResult;
        }
        return findNode(root->right, target);
    }
};

Complexity Analysis:

• Time Complexity: O(N)
  • Parent Mapping: O(N), where N is the number of nodes in the tree.
  • Finding Target Node: O(N), as we traverse the tree to find the target.
  • Burn Simulation (BFS): O(N), as we visit each node once.
  • Overall: O(N)
• Space Complexity: O(N)
  • Parent Map: O(N)
  • Queue for BFS: O(N) in the worst case.
  • Visited Set: O(N)
  • Overall: O(N)