Minimum Time to Burn Binary Tree
Hard Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Minimum time taken to BURN the Binary Tree from a Node, Binary Tree, Traversal, Breadth-First Search, Graph, Queue, Time Complexity, Space Complexity, space complexity, level order traversal, general programming, binary tree, time complexity analysis, graph theory, bfs, tree traversal, Nodes at Distance K.
Minimum Time to Burn a Binary Tree Given the root of a binary tree and an integer target, representing the value of a node in the tree, your task is to find the minimum time required to burn the entire tree. When a node burns, all its directly adjacent nodes (parent, left child, and right child) also catch fire in the next unit of time. The fire starts at the target node. Input Specification: The first line contains a string representation of the binary tree in level order traversal. 'null' indicates a missing child. The second line contains an integer target, the value of the node from which the fire starts. Output Specification: Return a single integer, the minimum time in minutes required to burn the entire tree. Constraints: The number of nodes in the tree will be between 1 and 10^5. Node values will be between 0 and 10^5. target will always be a valid node value present in the tree. Each node value is unique. Sample Test Case: Input: Output: Explanation: The tree structure for the given input [1,2,3,4,null,null,null,5,6,7] is: 1 / \ 2 3 / \ 4 null / \ 5 6 / 7 Starting the fire from node 4: Time 0: Node 4 burns. Time 1: Node 2 (parent of 4), Node 5 (left child of 4), Node 6 (right child of 4) burn. Time 2: Node 1 (parent of 2), Node 3 (right child of 1), Node 7 (left child of 6) burn. Time 3: Nothing else to burn. All nodes reachable from the initial fire source have burned. The maximum time taken is 3 minutes (e.g., path 4 2 1 3 or 4 6 7).