# 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:

1. A node will burn only once.
2. Every node takes same time for burning.

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)) {
}
else {
Set<Integer> set = new HashSet<>();
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
``````