Minimum Time taken to completely burn the binary tree (code in JAVA)
import java.util.*;
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;
}
}
public class h {
static class BinaryTree {
static TreeNode buildTree(Scanner scanner, String position, int parentValue) {
System.out.print("Add " + position + " TreeNode for " + parentValue + " (y/n): ");
String userChoice = scanner.next();
if (userChoice.equalsIgnoreCase("y")) {
System.out.print("Enter " + position + " TreeNode value: ");
int TreeNodeValue = scanner.nextInt();
TreeNode newTreeNode = new TreeNode(TreeNodeValue);
newTreeNode.left = buildTree(scanner, "left", TreeNodeValue);
newTreeNode.right = buildTree(scanner, "right", TreeNodeValue);
return newTreeNode;
} else {
return null;
}
}
}
public static int minTimeToBurn(TreeNode root, int target) {
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
buildParentMap(root, null, parentMap);
TreeNode targetNode = findTargetNode(root, target);
Queue<TreeNode> queue = new LinkedList<>();
queue.add(targetNode);
Set<TreeNode> visited = new HashSet<>();
visited.add(targetNode);
int time = 0;
while (!queue.isEmpty()) {
int size = queue.size();
boolean burned = false;
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (current.left != null && !visited.contains(current.left)) {
queue.add(current.left);
visited.add(current.left);
burned = true;
}
if (current.right != null && !visited.contains(current.right)) {
queue.add(current.right);
visited.add(current.right);
burned = true;
}
TreeNode parent = parentMap.get(current);
if (parent != null && !visited.contains(parent)) {
queue.add(parent);
visited.add(parent);
burned = true;
}
}
if (burned) {
time++;
}
}
return time;
}
public static void buildParentMap(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {
if (node == null) {
return;
}
parentMap.put(node, parent);
buildParentMap(node.left, node, parentMap);
buildParentMap(node.right, node, parentMap);
}
public static TreeNode findTargetNode(TreeNode node, int target) {
if (node == null) {
return null;
}
if (node.val == target) {
return node;
}
TreeNode left = findTargetNode(node.left, target);
TreeNode right = findTargetNode(node.right, target);
return left != null ? left : right;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BinaryTree bt = new BinaryTree();
System.out.print("Enter root node value: ");
int rootValue = scanner.nextInt();
TreeNode root = new TreeNode(rootValue);
root.left = bt.buildTree(scanner, "left", rootValue);
root.right = bt.buildTree(scanner, "right", rootValue);
System.out.println("Tree construction complete.");
int target = 5; // take node of your choice from where you have to burn
int time = minTimeToBurn(root, target);
System.out.println("Time taken for the tree to burn from TreeNode " + target + ": " + time);
scanner.close();
}
}
No comments:
Post a Comment