Binary Tree: Given a binary tree and a target, burn it

Problem Statement:

Given a binary tree and a target, burn it.

Below is the burning sequence.

Fire will spread to the connected nodes.

Each node will burn only once.

You need to print the sequence of entire tree burning

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Target: 12

Output:

Minute 0: 14 
Minute 1: 12 
Minute 2: 11 10 
Minute 3: 8 
Minute 4: 9 2 

Solution Explanation:

We will solve using BFS.

For that, we will create a adjacency list for each node.

Node will be the key, value will be the node value of its parent, left child and right child.

Now for the BFS:

Start by adding the start node into the queue and take a visited array to keep track of the visited nodes.

Then traverse level by level and count the number of level required to visit all reachable nodes.

During the traversal, get the adjacent nodes from the map and push the unvisted nodes into the queue.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

void convert(Node* current, int parent, unordered_map<int, unordered_set<int>>& map) 
{
    if (current == nullptr) 
    {
        return;
    } 

    if (map.find(current->data) == map.end()) 
    {
        map[current->data] = unordered_set<int>();
    }
    unordered_set<int>& adjacentList = map[current->data];

    if (parent != 0) 
    {
        adjacentList.insert(parent);
    } 
    if (current->left != nullptr) 
    {
        adjacentList.insert(current->left->data);
    } 
    if (current->right != nullptr) 
    {
        adjacentList.insert(current->right->data);
    }
    convert(current->left, current->data, map);
    convert(current->right, current->data, map);
}

int solution(Node* root, int start) 
{
    unordered_map<int, unordered_set<int>> map;
    convert(root, 0, map);

    queue<int> q;
    q.push(start);
    int minute = 0;
    unordered_set<int> visited;
    visited.insert(start);

    while (!q.empty()) 
    {
        int levelSize = q.size();
        cout << "Minute " << minute << ": ";
        vector<int> burntNodes;

        while (levelSize > 0) 
        {
            int current = q.front();
            q.pop();
            burntNodes.push_back(current);

            for (int num : map[current]) 
            {
                if (visited.find(num) == visited.end()) 
                {
                    visited.insert(num);
                    q.push(num);
                }
            }
            levelSize--;
        }

        // Print all nodes burnt at this minute
        for (int node : burntNodes) 
        {
            cout << node << " ";
        }
        cout << endl;

        minute++;
    }
    return minute - 1;
}


int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    solution(root, 14);
    
    return 0;
}

Output

Minute 0: 14 
Minute 1: 12 
Minute 2: 11 10 
Minute 3: 8 
Minute 4: 9 2