Summary of "L31. Minimum time taken to BURN the Binary Tree from a Node | C++ | Java"

Summary of the Video: “L31. Minimum time taken to BURN the Binary Tree from a Node | C++ | Java”

Main Idea

The video explains how to find the minimum time required to burn an entire binary tree starting from any given node. The burning spreads to adjacent nodes (left child, right child, and parent) simultaneously each second. The goal is to determine the total time until the whole tree is burnt.

Key Concepts and Problem Explanation

The problem involves burning a binary tree starting from a given node.
Burning spreads every second to adjacent nodes: left child, right child, and parent.
The time to burn the entire tree is the number of steps until all nodes are burnt.
The problem can be asked for any node, including leaf nodes.
Burning progresses level-wise (simultaneously to all neighbors), so BFS (Breadth-First Search) is the appropriate traversal method, not DFS.
Upward traversal (to parent nodes) is not straightforward because binary trees only have pointers downwards (to children).
To enable upward traversal, parent pointers must be assigned or stored.

Methodology / Algorithm Steps

Assign Parent Pointers
- Perform a level order traversal (BFS) starting from the root.
- For each node, record its parent in a hash map or dictionary.
- This allows moving upward during the burning process.
Find the Target Node
- If only the value of the node is given (not the address), traverse the tree to find the actual node address.
- This is done during the parent-mapping BFS itself by checking node values.
Burning Process Using BFS
- Initialize a queue and insert the starting node (the node from which burning begins).
- Maintain a visited map to track burnt nodes.
- Set time = 0 initially.
- While the queue is not empty:
  - For each node in the current queue (all nodes burning at the current time):
    - Burn adjacent nodes: left child, right child, and parent (if not already burnt).
    - Mark newly burnt nodes as visited and add them to the queue.
  - If at least one new node is burnt in this iteration, increment the time by 1.
- When no more nodes can be burnt (queue empty), the current time value is the minimum time to burn the entire tree.
Why BFS and Not DFS?
- Burning happens simultaneously to all adjacent nodes.
- BFS naturally simulates this level-wise spreading of fire.
- DFS would not correctly model simultaneous burning as it explores depth-first.

Code Explanation (C++ / Java)

The code has two main parts:
1. Parent Mapping BFS:
  - Maps each node to its parent.
  - Finds and returns the target node’s address.
2. Burning BFS:
  - Starts from the target node.
  - Uses a queue and visited map.
  - Burns adjacent nodes level by level.
  - Tracks time until no new nodes are burnt.
Time Complexity: O(N), where N is the number of nodes.
Space Complexity: O(N) due to the queue, visited map, and parent map.

Summary of Steps

Step 1: Perform BFS from root to:
- Map each node to its parent.
- Find the target node by value.
Step 2: Initialize BFS queue with the target node.
Step 3: Maintain a visited map to track burnt nodes.
Step 4: While queue not empty:
- For each node in the current level:
  - Burn left child if unvisited.
  - Burn right child if unvisited.
  - Burn parent if unvisited.
- If any node burnt in this iteration, increment time.
Step 5: Return the time after BFS completes.