Minimum time to burn a Tree starting from a Leaf node
Given a binary tree and a leaf node from this tree. It is known that in 1s all nodes connected to a given node (left child, right child, and parent) get burned in 1 second. Then all the nodes which are connected through one intermediate get burned in 2 seconds, and so on. The task is to find the minimum time required to burn the complete binary tree.
Examples:
Input : 1 / \ 2 3 / \ \ 4 5 6 / \ \ 7 8 9 \ 10 Leaf = 8 Output : 7 Initially 8 is set to fire at 0th sec. 1 / \ 2 3 / \ \ 4 5 6 / \ \ 7 F 9 \ 10 After 1s: 5 is set to fire. 1 / \ 2 3 / \ \ 4 F 6 / \ \ 7 F 9 \ 10 After 2s: 2, 7 are set to fire. 1 / \ F 3 / \ \ 4 F 6 / \ \ F F 9 \ 10 After 3s: 4, 1 are set to fire. F / \ F 3 / \ \ F F 6 / \ \ F F 9 \ 10 After 4s: 3 is set to fire. F / \ F F / \ \ F F 6 / \ \ F F 9 \ 10 After 5s: 6 is set to fire. F / \ F F / \ \ F F F / \ \ F F 9 \ 10 After 6s: 9 is set to fire. F / \ F F / \ \ F F F / \ \ F F F \ 10 After 7s: 10 is set to fire. F / \ F F / \ \ F F F / \ \ F F F \ F It takes 7s to burn the complete tree.
Approach: The idea is to store additional information for every node:
- Depth of left subtree.
- Depth of right subtree.
- The time required for the fire to reach the current node starting from the first leaf node burned.
- A boolean variable to check if the initial burnt node is in the tree rooted under current node.
Before moving ahead with the approach let’s take a look at the tree below:
1 / \ 2 3 / \ / 4 5 6 / / \ 8 9 10 / 11
In the above tree, if we set the leaf node 11 at fire.
- In 1s, the fire will reach node 9.
- In 2s, the fire will reach node 5.
- In 3rd second, the fire will reach node 2 and 10. Here comes an observation:
- In 2s fire reached node 5. For node 5, the initial burned leaf is in it’s left subtree, so the time taken to burn right subtree will be the height of the right subtree which is 1. Therefore, fire reaches to node 10 in (2+1) = 3s.
- Again, for node 2. Fire reached to node 2 in 3s from right subtree. Therefore, time taken to burn left subtree will be it’s height.
So the solution is to apply recursion and for every node calculate the below-required values:
- Left Depth.
- Right Depth.
- The time required for fire to reach the current node.
- Is the current subtree contains initial burnt leaf node.
So, for the minimum time required to burn any subtree will be:
The time required for fire to reach the root node from initial burnt leaf + depth of the opposite side
Therefore, to find time required to burn the complete tree, we need to calculate the above value for every node, and take maximum of that value.
ans = max(ans, (time required for fire to reach current node + depth of other subtree))
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Structure of a tree node struct Node { int key; struct Node* left; struct Node* right; Node( int k) { key = k; left = right = NULL; } }; int res = 0; // Function to find the time for the tree to burn int burnTime(Node* root, int leaf, int & dist) { if (root == NULL) return 0; if (root->key == leaf) { dist = 0; return 1; } int ldist = -1, rdist = -1; int lh = burnTime(root->left, leaf, ldist); int rh = burnTime(root->right, leaf, rdist); if (ldist != -1) { dist = ldist + 1; res = max(res, dist + rh); } else if (rdist != -1) { dist = rdist + 1; res = max(res, dist + lh); } return max(lh, rh) + 1; } // Driver code int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->left->left->left = new Node(8); root->left->right->left = new Node(9); root->left->right->right = new Node(10); root->left->right->left->left = new Node(11); int dist = -1; int target = 11; burnTime(root, target, dist); cout << res; return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver code public static void main(String args[]) { Node root = new Node( 1 ); root.left = new Node( 2 ); root.right = new Node( 3 ); root.left.left = new Node( 4 ); root.left.right = new Node( 5 ); root.right.left = new Node( 6 ); root.left.left.left = new Node( 8 ); root.left.right.left = new Node( 9 ); root.left.right.right = new Node( 10 ); root.left.right.left.left = new Node( 11 ); Distance dist = new Distance(- 1 ); int target = 11 ; burnTime(root, target, dist); System.out.print(res); } static int res = 0 ; // Function to find the time to burn public static int burnTime(Node root, int leaf, Distance dist) { if (root == null ) return 0 ; if (root.key == leaf) { dist.val = 0 ; return 1 ; } Distance ldist = new Distance(- 1 ), rdist = new Distance(- 1 ); int lh = burnTime(root.left, leaf, ldist); int rh = burnTime(root.right, leaf, rdist); if (ldist.val != - 1 ) { dist.val = ldist.val + 1 ; res = Math.max(res, dist.val + rh); } else if (rdist.val != - 1 ) { dist.val = rdist.val + 1 ; res = Math.max(res, dist.val + lh); } return Math.max(lh, rh) + 1 ; } } // Class to define a node of the tree class Node { int key; Node left; Node right; Node( int k) { key = k; left = right = null ; } } class Distance { int val; Distance( int d) { val = d; } } |
Python3
# Python Program for Lowest Common Ancestor in a Binary Tree # O(n) solution to find LCS of two given values n1 and n2 # A binary tree node class Node: # Constructor to create a new binary node def __init__( self , key): self .key = key self .left = None self .right = None res = 0 # Function to find out the time to burn the tree def burnTime(root, leaf, dist): if (root is None ): return 0 if (root.key = = leaf): dist[ 0 ] = 0 return 1 ldist, rdist = [ - 1 ], [ - 1 ] lh = burnTime(root.left, leaf, ldist) rh = burnTime(root.right, leaf, rdist) global res if (ldist[ 0 ] ! = - 1 ): dist[ 0 ] = ldist[ 0 ] + 1 res = max (res, dist[ 0 ] + rh) # print(res) elif (rdist[ 0 ] ! = - 1 ): dist[ 0 ] = rdist[ 0 ] + 1 res = max (res, dist[ 0 ] + lh) # print(res) return max (lh, rh) + 1 # Driver program to test above function # Let's create the Binary Tree shown in above diagram if __name__ = = '__main__' : root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.left = Node( 6 ) root.left.left.left = Node( 8 ) root.left.right.left = Node( 9 ) root.left.right.right = Node( 10 ) root.left.right.left.left = Node( 11 ) dist = [ - 1 ] target = 11 burnTime(root, target, dist) print (res) |
C#
// C# program to find minimum time required // to burn the binary tree completely using System; class GFG { // Tree Node class Node { public int data; public Node left, right; public Node( int data) { this .data = data; this .left = null ; this .right = null ; } } /* ***********ADDITIONAL INFO************* lDepth - maximum height of left subtree rDepth - maximum height of right subtree contains - stores true if tree rooted at current node contains the first burnt node time - time to reach fire from the initially burnt leaf node to this node */ class Data { public int leftDepth, rightDepth, time; public bool contains; public Data() { contains = false ; leftDepth = rightDepth = 0; time = -1; } } /* Function to calculate time required to burn tree completely node - address of current node info - extra information about current node target - node that is fired res - stores the result */ static void getResult(Node node, Data data, int target) { // Base case: if root is null if (node == null ) { return ; } // If current node is leaf if (node.left == null && node.right == null ) { // If current node is the first burnt node if (node.data == target) { data.contains = true ; data.time = 0; } return ; } // Information about left child Data leftData = new Data(); getResult(node.left, leftData, target); // Information about right child Data rightData = new Data(); getResult(node.right, rightData, target); // If left subtree contains the fired node then // time required to reach fire to current node // will be (1 + time required for left child) data.time = (leftData.contains) ? (leftData.time + 1) : -1; // If right subtree contains the fired node then // time required to reach fire to current node // will be (1 + time required for right child) if (data.time == -1) data.time = (rightData.contains) ? (rightData.time + 1) : -1; // Storing(true or false) if the tree rooted at // current node contains the fired node data.contains = (leftData.contains || rightData.contains); // Calculate the maximum depth of left subtree data.leftDepth = (node.left == null ) ? 0 : (1 + Math.Max(leftData.leftDepth, leftData.rightDepth)); // Calculate the maximum depth of right subtree data.rightDepth = (node.right == null ) ? 0 : (1 + Math.Max(rightData.leftDepth, rightData.rightDepth)); // Calculating answer if (data.contains) { // If left subtree exists and // it contains the fired node if (leftData.contains) { // calculate result res = Math.Max(res, data.time + data.rightDepth); } // If right subtree exists and it // contains the fired node if (rightData.contains) { // calculate result res = Math.Max(res, data.time + data.leftDepth); } } } // To store the result public static int res; // Driver Code public static void Main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.left.left.left = new Node(8); root.left.right.left = new Node(9); root.left.right.right = new Node(10); root.left.right.left.left = new Node(11); int target = 11; res = 0; getResult(root, new Data(), target); Console.WriteLine(res); } } // This code is contributed by PrinciRaj1992 |
Javascript
// Definition of the Node class class Node { constructor(k) { this .key = k; this .left = null ; this .right = null ; } } let res = 0; // Function to find the time for the tree to burn function burnTime(root, leaf, dist) { if (!root) { return 0; } if (root.key === leaf) { dist.val = 0; return 1; } let ldist = {val: -1}, rdist = {val: -1}; let lh = burnTime(root.left, leaf, ldist); let rh = burnTime(root.right, leaf, rdist); if (ldist.val !== -1) { dist.val = ldist.val + 1; res = Math.max(res, dist.val + rh); } else if (rdist.val !== -1) { dist.val = rdist.val + 1; res = Math.max(res, dist.val + lh); } return Math.max(lh, rh) + 1; } // Driver code let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.left.left.left = new Node(8); root.left.right.left = new Node(9); root.left.right.right = new Node(10); root.left.right.left.left = new Node(11); let dist = {val: -1}; let target = 11; burnTime(root, target, dist); console.log(res); |
6
Another Approach: We can relate this problem to Min distance between two given nodes of a Binary Tree. The only thing here changes is we have to find the maximum distance between the target node and leaf nodes.
Algo:
- Create a hashmap and find the node to parent mapping.
- Make pointers that will point to the node having a value target.
- Write a function that will call recursively to itself and returns the distance to all leaf nodes.
- Return the maximum distance among them.
C++
// C++ program to find minimum time required // to burn the binary tree completely #include <bits/stdc++.h> using namespace std; // Tree Node struct Node { int data; Node* left; Node* right; Node() { left = NULL; right = NULL; } }; // Utility function to create a new Node Node* newNode( int val) { Node* temp = new Node; temp->data = val; return temp; } Node* n1 = NULL; /* Should return minimum distance between a and b in a tree with given root*/ void getparent(Node* root, Node* parent, map<Node*, Node*>& map) { if (root == NULL) return ; map[root] = parent; getparent(root->left, root, map); getparent(root->right, root, map); return ; } void getnode(Node* root, int a) { if (root == NULL) return ; if (root->data == a) n1 = root; getnode(root->left, a); getnode(root->right, a); return ; } int getmaxdis(Node* target, int dis, map<Node*, int > vis, map<Node*, Node*>& map) { if (target == NULL) return dis - 1; if (vis.find(target) != vis.end()) return INT_MIN; // calls // calls vis[target] = 1; int a1 = INT_MIN; int a2 = INT_MIN; int a3 = INT_MIN; // if(a->left!=NULL) a1 = getmaxdis(target->left, dis + 1, vis, map); // left child // if(a->right!=NULL) a2 = getmaxdis(target->right, dis + 1, vis, map); // right child // if(map[a] != NULL) a3 = getmaxdis(map[target], dis + 1, vis, map); // parent return max(max(a1, a2), a3); } int minTime(Node* root, int target) { map<Node*, Node*> par; getparent(root, NULL, par); getnode(root, target); map<Node*, int > vis; return getmaxdis(n1, 0, vis, par); } // Driver Code int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->left->left->left = newNode(8); root->left->right->left = newNode(9); root->left->right->right = newNode(10); root->left->right->left->left = newNode(11); // target node is 8 int target = 11; cout << minTime(root, target); return 0; } // This code is contributed by Arpit Jain |
Java
// Java program for the above approach import java.util.*; public class Main { // Tree Node static class Node { int data; Node left; Node right; Node() { left = null ; right = null ; } } // Utility function to create a new Node static Node newNode( int val) { Node temp = new Node(); temp.data = val; return temp; } static Node n1 = null ; /* Should return minimum distance between a and b in a tree with given root*/ static void getparent(Node root, Node parent, Map<Node, Node> map) { if (root == null ) return ; map.put(root, parent); getparent(root.left, root, map); getparent(root.right, root, map); return ; } static void getnode(Node root, int a) { if (root == null ) return ; if (root.data == a) n1 = root; getnode(root.left, a); getnode(root.right, a); return ; } static int getmaxdis(Node target, int dis, Map<Node, Integer> vis, Map<Node, Node> map) { if (target == null ) return dis - 1 ; if (vis.containsKey(target)) return Integer.MIN_VALUE; // calls // calls vis.put(target, 1 ); int a1 = Integer.MIN_VALUE; int a2 = Integer.MIN_VALUE; int a3 = Integer.MIN_VALUE; // if(a->left!=NULL) a1 = getmaxdis(target.left, dis + 1 , vis, map); // left child // if(a->right!=NULL) a2 = getmaxdis(target.right, dis + 1 , vis, map); // right child // if(map[a] != NULL) a3 = getmaxdis(map.get(target), dis + 1 , vis, map); // parent return Math.max(Math.max(a1, a2), a3); } static int minTime(Node root, int target) { Map<Node, Node> par = new HashMap<>(); getparent(root, null , par); getnode(root, target); Map<Node, Integer> vis = new HashMap<>(); return getmaxdis(n1, 0 , vis, par); } // Driver code public static void main(String[] args) { Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); root.right.left = newNode( 6 ); root.left.left.left = newNode( 8 ); root.left.right.left = newNode( 9 ); root.left.right.right = newNode( 10 ); root.left.right.left.left = newNode( 11 ); // target node is 11 int target = 11 ; System.out.println(minTime(root, target)); } } // This code is contributed by Potta Lokesh |
Python3
# Python Program for Lowest Common Ancestor in a Binary Tree # O(n) solution to find LCS of two given values n1 and n2 # A binary tree node class Node: # Constructor to create a new binary node def __init__( self , key): self .data = key self .left = None self .right = None n1 = None # Function to find out the time to burn the tree class Solution: def maximum( self ,a, b, c): list = [a, b, c] return max ( list ) def getparent( self ,root, parent, par): if (root = = None ): return par[root] = parent; self .getparent(root.left, root, par); self .getparent(root.right, root, par); return ; def getnode( self ,root,a): global n1 if (root = = None ): return if (root.data = = a): n1 = root; self .getnode(root.left, a); self .getnode(root.right, a); return ; def getmaxdis( self ,target,dis,vis,par): if (target = = None ): return dis - 1 ; if (target in vis): return - 10000000 ; vis[target] = 1 ; a1 = - 10000000 a2 = - 10000000 a3 = - 10000000 a1 = self .getmaxdis(target.left, dis + 1 , vis, par) a2 = self .getmaxdis(target.right, dis + 1 , vis, par) a3 = self .getmaxdis(par[target], dis + 1 , vis, par); return self .maximum(a1,a2,a3) def minTime( self , root,target): # code here par = {} self .getparent(root, None , par) self .getnode(root, target); vis = {} global n1 ans = self .getmaxdis(n1, 0 , vis, par) return ans # Driver program to test above function # Let's create the Binary Tree shown in above diagram if __name__ = = '__main__' : root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.left = Node( 6 ) root.left.left.left = Node( 8 ) root.left.right.left = Node( 9 ) root.left.right.right = Node( 10 ) root.left.right.left.left = Node( 11 ) target = 11 res = Solution().minTime(root,target) print (res) # This code is contributed by Arpit Jain |
C#
using System; using System.Collections.Generic; class GFG { // Tree Node public class Node { public int data; public Node left; public Node right; public Node() { left = null ; right = null ; } } // Utility function to create a new Node public static Node newNode( int val) { Node temp = new Node(); temp.data = val; return temp; } public static Node n1 = null ; /* Should return minimum distance between a and b in a tree with given root*/ public static void getparent(Node root, Node parent, Dictionary<Node, Node> map) { if (root == null ) return ; map[root] = parent; getparent(root.left, root, map); getparent(root.right, root, map); return ; } public static void getnode(Node root, int a) { if (root == null ) return ; if (root.data == a) n1 = root; getnode(root.left, a); getnode(root.right, a); return ; } public static int getmaxdis(Node target, int dis, Dictionary<Node, int > vis, Dictionary<Node, Node> map) { if (target == null ) return dis - 1; if (vis.ContainsKey(target)) return int .MinValue; // calls // calls vis[target] = 1; int a1 = int .MinValue; int a2 = int .MinValue; int a3 = int .MinValue; // if(a->left!=NULL) a1 = getmaxdis(target.left, dis + 1, vis, map); // left child // if(a->right!=NULL) a2 = getmaxdis(target.right, dis + 1, vis, map); // right child // if(map[a] != NULL) a3 = getmaxdis(map[target], dis + 1, vis, map); // parent return Math.Max(Math.Max(a1, a2), a3); } public static int minTime(Node root, int target) { Dictionary<Node, Node> par = new Dictionary<Node, Node>(); getparent(root, null , par); getnode(root, target); Dictionary<Node, int > vis = new Dictionary<Node, int >(); return getmaxdis(n1, 0, vis, par); } public static void Main() { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.left.left.left = newNode(8); root.left.right.left = newNode(9); root.left.right.right = newNode(10); root.left.right.left.left = newNode(11); // target node is 11 int target = 11; Console.WriteLine(minTime(root, target)); } } // This code is contributed by poojaagarwal2. |
Javascript
// JavaScript program to find minimum time required // to burn the binary tree completely // Tree Node class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } let n1 = null ; // Utility function to create a new Node function newNode(val) { let temp = new Node(val); return temp; } /* Should return minimum distance between a and b in a tree with given root*/ function getParent(root, parent, map) { if (root == null ) return ; map.set(root, parent); getParent(root.left, root, map); getParent(root.right, root, map); return ; } function getNode(root, a) { if (root == null ) return ; if (root.data == a) n1 = root; getNode(root.left, a); getNode(root.right, a); return ; } function getMaxDis(target, dis, vis, map) { if (target == null ) return dis - 1; if (vis.has(target)) return -Infinity; vis.set(target, 1); let a1 = -Infinity; let a2 = -Infinity; let a3 = -Infinity; // if (target.left) a1 = getMaxDis(target.left, dis + 1, vis, map); // if (target.right) a2 = getMaxDis(target.right, dis + 1, vis, map); // if (map.has(target)) a3 = getMaxDis(map.get(target), dis + 1, vis, map); return Math.max(Math.max(a1, a2), a3); } function minTime(root, target) { let par = new Map(); getParent(root, null , par); getNode(root, target); let vis = new Map(); return getMaxDis(n1, 0, vis, par); } // Driver Code let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.left.left.left = newNode(8); root.left.right.left = newNode(9); root.left.right.right = newNode(10); root.left.right.left.left = newNode(11); let target = 11; console.log(minTime(root, target)); // This code is contributed by rutikbhosale |
6
Time Complexity: O(n) since we are traversing the tree in all three directions from the target node.
Auxiliary Space: O(n) since we are storing the parent of each node.