# Burning binary tree

## Burn the Binary tree starting from the target node

You have given a binary tree and a target node value. Now you have to burn the tree from target node. You have to print the sequence in which the tree will burn.

**There are some conditions:**

- A node will burn only once.
- Every node takes same time for burning.
- Fire will spread through adjacent nodes only

**Input-**

Target node = 4

**Output-**

```
4
2 3 5
0 6
8
7 9
```

**Explanation-** First, the node with value 4 will burn so, it is printed first. After that 2, 3, 5 nodes will catch fire at same time so, they printed in same line. In this way, full tree is burnt.

## Concept behind the solution

First, we find the target node by recursion then we store right and left child using a queue. After that we will use this queue to print the burning tree.

**Code -**

**// CPP program to print the nodes of burning tree**

**Program in C++**

```
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
int burnTreeUtil(Node* root, int target, queue<Node*>& q)
{
if (root == NULL) {
return 0;
}
if (root->key == target) {
cout << root->key << endl;
if (root->left != NULL) {
q.push(root->left);
}
if (root->right != NULL) {
q.push(root->right);
}
return 1;
}
int a = burnTreeUtil(root->left, target, q);
if (a == 1) {
int qsize = q.size();
while (qsize--) {
Node* temp = q.front();
cout << temp->key << " , ";
q.pop();
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
if (root->right != NULL)
q.push(root->right);
cout << root->key << endl;
return 1;
}
int b = burnTreeUtil(root->right, target, q);
if (b == 1) {
int qsize = q.size();
while (qsize--) {
Node* temp = q.front();
cout << temp->key << " , ";
q.pop();
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
if (root->left != NULL)
q.push(root->left);
cout << root->key << endl;
return 1;
}
}
void burnTree(Node* root, int target)
{
queue<Node*> q;
burnTreeUtil(root, target, q);
while (!q.empty()) {
int qSize = q.size();
while (qSize > 0) {
Node* temp = q.front();
cout << temp->key;
if (temp->left != NULL) {
q.push(temp->left);
}
if (temp->right != NULL) {
q.push(temp->right);
}
if (q.size() != 1)
cout << " , ";
q.pop();
qSize--;
}
cout << endl;
}
}
int main()
{
Node* root = newNode(10);
root->left = newNode(12);
root->right = newNode(13);
root->right->left = newNode(14);
root->right->right = newNode(15);
root->right->left->left = newNode(21);
root->right->left->right = newNode(22);
root->right->right->left = newNode(23);
root->right->right->right = newNode(24);
int targetNode = 14;
burnTree(root, targetNode);
return 0;
}
```

**// JAVA program to print the nodes of burning tree**

**Program in Java**

```
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right)
{
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public static int search(TreeNode root,
int num,
Map<Integer,
Set<Integer> > lm)
{
if (root != null)
{
if (root.val == num)
{
levelOrderStoredInMap(root.left, 1,
lm);
levelOrderStoredInMap(root.right, 1,
lm);
return 1;
}
int k = search(root.left, num, lm);
if (k > 0)
{
storeRootAtK(root, k, lm);
levelOrderStoredInMap(root.right, k + 1,
lm);
return k + 1;
}
k = search(root.right, num, lm);
if (k > 0)
{
storeRootAtK(root, k, lm);
levelOrderStoredInMap(root.left, k + 1,
lm);
return k + 1;
}
}
return -1;
}
public static void levelOrderStoredInMap(
TreeNode root, int k,
Map<Integer, Set<Integer> > lm)
{
if (root != null) {
storeRootAtK(root, k, lm);
levelOrderStoredInMap(root.left, k + 1,
lm);
levelOrderStoredInMap(root.right, k + 1,
lm);
}
}
private static void
storeRootAtK(TreeNode root, int k,
Map<Integer, Set<Integer> > lm)
{
if (lm.containsKey(k)) {
lm.get(k).add(root.val);
}
else {
Set<Integer> set = new HashSet<>();
set.add(root.val);
lm.put(k, set);
}
}
public static void main(String[] args)
{
TreeNode root = new TreeNode(12);
root.left = new TreeNode(13);
root.right = new TreeNode(10);
root.right.left = new TreeNode(14);
root.right.right = new TreeNode(15);
TreeNode left = root.right.left;
TreeNode right = root.right.right;
left.left = new TreeNode(21);
left.right = new TreeNode(24);
right.left = new TreeNode(22);
right.right = new TreeNode(23);
Map<Integer, Set<Integer> > lm
= new HashMap<>();
search(root, 14, lm);
System.out.println(14);
for (Integer level : lm.keySet())
{
for (Integer val : lm.get(level))
{
System.out.print(val + " ");
}
System.out.println();
}
}
}
```

**Output-**

```
14
21 , 22 , 13
15 , 10
23 , 24 , 12
```