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.
3. 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