Burn a Tree | Minimum Time To Burn A Binary Tree Starting From The Leaf Node | DSA-One Course #65

Hey guys, In this video, We're going to solve an interesting problem called: Minimum Time To Burn A Binary Tree Starting From The Leaf Node.
Use the code ANUJBHAIYA on GeeksforGeeks to avail discount on courses.
🥳 Join our Telegram Community:
Telegram channel: telegram.me/realanujbhaiya
Telegram group: telegram.me/dsa_one
Follow me on:
Instagram: / anuj.kumar.sharma
Linkedin: / sharma-kumar-anuj
Twitter: / realanujbhaiya
Complete DSA Playlist:
DSA-One course: • Time Complexity & Big ...
Complete Android Development Playlist: • Android Development Tu...
Hashtags:
#anujbhaiya #dsaone
Tags:
burn a tree
anuj bhaiya
burning tree
burn a binary tree
anuj bhaiya java
minimum cost tree from leaf values
binary tree in data structure
binary tree
burn tree
burning tree gfg
apna college
burn a tree interviewbit
burn binary tree
java by anuj bhaiya
time to burn
tree dsa
tree in data structure
akshay saini
anuj
love babbar
minimum depth of binary tree
minimum time to burn a tree
threaded binary tree in data structure
tree
tree algorithms
tree in dsa
anuj bhaiya dsa
anuj dsa
anuj kumar sharma
apna college python
binary tree c++
binary tree in java
binary tree playlists
boundary of binary tree
boundary traversal of binary tree
bst iterator
burning trees
coding ninjas
depth of binary tree
diameter of binary tree
dsp anuj bhaiya
flattening a linked list
game theory
geeksforgeeks
graph java
inorder traversal binary tree
java anuj bhaiya
kunal kushwaha
maximum path sum in binary tree
news views & updates
node
prim's algorithm for minimum spanning trees
seed it solution
top view of binary tree
tree burning
tree in python
trees in dsa

[@harshabhardwaj7525]

why your course “JAVA| DSA + ALGO” got removed from apni kaksha?? i was following that course and was not able to complete it cz it got removed. can u please tell me where can i find it?

[@sahilhansofficial]

Sir android studio waali playlist ke last app pe hu uske baad kha se practice kr skte h? Ya koi course krna chahiye, pls suggest😊

[@RiteshSingh-rz7tz]

Thanks for continuing this series. I am addicted to it.

[@laveshgarg2189]

Thanku Bhaiya for the amazing consistency in dsa one course

[@aishwaryshukla8880]

Bhaiya this code is not working on gfg practice! I modified the code so that it handles when we burn from the root node itself but still a test case is failing where the tree is skewed. PLEASE DO CORRECTION 🙏🏻🛑⭕🛑⭕🛑⭕🛑⭕

[@abhinavvarshney6366]

.... THANK YOU ANUJ BHAIYA....

[@nittinrana2277]

Bahiya thanks for maintaining consistency

[@laveshgarg2189]

Bhaiya the approach was mind blowing maza aa gaya Thanku Bhaiya

[@reenayadav8468]

Thank you sir

[@abacas2175]

First comment... Bhayiya java complete course daliya please..i like ur way of teaching!!!!

[@Lifeofkashh31]

agya samjh rhanks a lot

[@pritamsarkar3371]

1st traverse the tree get all parents in a hash map , 2nd find that node, from where to start, 3rd apply bfs including left child, right child, and parent then get the maximum level from that, that will be the burning time, Thank u anuj Bhai

[@pritamsarkar3371]

1st and second step can be done together using a global node type variable

[@sdwivedi]

Thanks bhaiya

[@hamzaansari5714]

Thank you bhai

[@sarangavadiya7087]

thank you bhaiya.

[@saritaprasad4295]

Thanks

[@subhamhazracreation5634]

Bhaiya plz apni kaksha k java playlist ko unhide karne k liye kahiye...atleast for a day download kar lunga.... 39 videos dekha tha uske baad sab hide kar diya gaya hai.... plz bhaiya.... yaha aapka dsa ka series kar raha hu...aur waha java kar raha tha.....

[@Sanyamjain77]

Thanks for this solution, Actually in yesterday's weekly contest this problem - "Amount of time for binary tree to get infected" came and I was not able to solve it. All the other channels were providing the (tree -> graph then bfs) solution. But, I wanted to solve the problem using recursion and simple tree traversal. Your video really helped me. Thanks a lot for your efforts.

[@rohandikshit2171]

Can you share that code, I am having some issues in getting all the test cases passed.

[@Sanyamjain77]

@@rohandikshit2171 Yeah sure, here it is: class Solution { static int ans; class Depth { int d; Depth(int d){ this.d = d; } } int height(TreeNode node){ if(node == null) return 0; int lh = height(node.left); int rh = height(node.right); return Math.max(lh, rh) + 1; } int helper(TreeNode node, int target, Depth depth){ if(node == null) return 0; if(node.val == target){ depth.d = 0; int lh = height(node.left); int rh = height(node.right); ans = Math.max(lh, rh); return 0; } Depth ld = new Depth(-1); Depth rd = new Depth(-1); int lh = helper(node.left, target, ld); int rh = helper(node.right, target, rd); if(ld.d > -1){ ans = Math.max(ld.d + 1 + rh, ans); depth.d = ld.d + 1; }else if(rd.d > -1){ ans = Math.max(rd.d + 1 + lh, ans); depth.d = rd.d + 1; } return Math.max(lh, rh) + 1; } public int amountOfTime(TreeNode root, int start) { helper(root, start, new Depth(-1)); return ans; } }

[@rohandikshit2171]

@@Sanyamjain77 Thanks👍

[@Sanyamjain77]

@@rohandikshit2171 You're welcome!

[@jagankumarpatra]

@@Sanyamjain77 galat he code gfg me chal nehi raha he

[@keshavkamalkarn1431]

Thankyou bhai for your guidance and Bhaiya Is data structure and algorithm different for different languages?

[@warriorgaming9509]

NO

[@aryanvarma2536]

Hello bhaiya

[@user-eq1kt3js6z]

Can we use greedy by taking the node which in the centre of the most depth path

[@annanyavijay4267]

Can we use static depth variable instead of making it a wrapper class?

[@sagarchawla4926]

Did you get the answer?

[@sadavarshsaini9801]

Bro m jab bhi kisi website se koi question karta hu tab mujhe question hi samjh nhi aata ki kya pucha h jab ki code mujhe aata rhta h but question nhi samjh pata kya pucha h isliye kbhi Kar nhi pata please guide me

[@Lifeofkashh31]

bhiya ye samajh ni aya kya karu@anuj bhiya can u explain why we are having static class sepaerately for that depth

[@bharatDarshaByDrone]

Felling First With 6 others

[@ashwiniskumar4275]

Will this work only for burn from leaf node or burn from any target node.

[@yashyadav7927]

same question ... bhaiya if u there plz reply us

[@sudhanshudubey7267]

bhaiya please make video on hackathons

[@laplinanayak7688]

how we can install jdk in chrombook please upload vedio on this topic

[@mrrishiraj88]

🙏👍👍

[@subhankarpal2800]

Sir I did this code on GFG Practice ,I understand whole logic after that I tried by my own but many times I got different result but now I wrote code as same as in your video but now still got different and , did not run any test case please help me sir , This is the Code Output --------------------------------------- 1 2 3 4 5 N 6 N N 7 8 N 9 10 11 N N N 12 N N N 13 8 Your Output: 8 Expected Output: 7 Main code ----------------------- static class Depth{ int d; public Depth(int d){ this.d = d; } } public static int minTime(Node root, int target) { // Your code goes here Depth depth = new Depth(-1); burn(root,target,depth); return ans; } static int ans = -1; public static int burn(Node root,int target,Depth depth){ if(root == null)return 0; if(root.data == target){ depth.d = 1; return 1; } Depth ld = new Depth(-1); Depth rd = new Depth(-1); int lh = burn(root.left,target,ld); int rh = burn(root.right,target,rd); if(ld.d != -1){ ans = Math.max(ans,ld.d+1+rh); depth.d = ld.d+1; } else if(rd.d != -1){ ans = Math.max(ans,rd.d+1+lh); depth.d = rd.d+1; } return Math.max(lh,rh)+1; }

[@geetikabhatnagar8113]

int burn(Node* root,int target,int &d){ if(root==NULL) return 0; int ld=-1; int rd=-1; int lh=burn(root->left,target,ld); int rh=burn(root->right,target,rd); if(ld!=-1){ ans=max(ans,ld+1+rh); d=ld+1; } else if(rd!=-1){ ans=max(ans,rd+1+lh); d=rd+1;} if(root->data==target){ d=0; //start depth from 0 ans=max(ans,max(lh,rh)); //add this for burn from any node return 0; }

[@pranavmittal8249]

Bhaiya ek video git commands ke uper bhi bna 😣

[@pkyadav6230]

7:24 that's ampersand ' &'

[@rhinoara7119]

Bhiya ek doubt, code meh ek 100 size ka array difine Kare tho vo constant space complexity mane jayega?

[@tusharsharma6712]

no

[@sagarchawla4926]

Yes

[@payaskakar3938]

Wonder how people come up with the approach in the interview, if they hadn't solved it before.😶

[@k9killer]

no one bro , and interview me standard questions hi puche jate hai , so worry not

[@ankushaviraj8292]

Bhaiya Java ka full course apni kasha pe show nahi hora hai kaha se dekhe

[@arpanmaheshwari2290]

First

[@chinmaychaudhari4143]

Bhaiya topic wise dsa ki ek question sheet banva do na ... That would help us lot to practice while learning dsa...

[@AjitSingh-rg3zu]

Sir, the solution you gave is working only for the cases in which burning of tree starts from leaf node. Could you please recheck it and confirm if the solution will run for all cases or not

[@akshaypatil8940]

I have modified it to make it right.

[@akshaypatil8940]

If (target == root.data) { Int height = Math.max (burnTree(root.right), burnTree(root.left)); ans = Math.max(ans, height); return 1; }

[@rajeevshetty8929]

@@akshaypatil8940 return ans

[@priyanshumohanty5261]

1:16 Poora ka poora tree swaha 😂

[@mdnayab5839]

Please suggest if we want to burn from root node???????🤔

[@yashwantdwala2918]

height of tree

[@aishwaryshukla8880]

@@yashwantdwala2918 bro skewed tree wala test case fir bhi fail ho rha hai gfg me

[@good114]

💕❤️

[@26.ritukumari64]

Swahaaa

[@lokeshhans5036]

Bhai me ak middle family se belong karta hu or mene ak laptop kharida 50000 ka 2 mahine Pehle or use ghar se koi chori karke le gya or college fess bhi nhi de abhi app meri help kr do plz 🙏🙏🙏🙏🙏

[@shyamal_maity]

Bhaiya apne wo video kyun delete kiya "Reply to apni kaksa" ? Apka koi dosh nhi hai. Darna to usko chahiye. We are with you. Love you ❤️ kzbin.info/www/bejne/iXybdYKJdrWCebs

[@dev_with_haresh]

Too hard 😢

[@i_nishantjain]

for those who are finding why this code isn't working, let me tell you if root itself is the target then it returns 1 hence it fails just edit the code a little bit move if condition at line 36 to line 53 and replace return 1 with ans = Math.max(lh, rh); code- public static int burn(Node root,int target,Depth depth){ if(root == null)return 0; Depth ld = new Depth(-1); Depth rd = new Depth(-1); int lh = burn(root.left,target,ld); int rh = burn(root.right,target,rd); if(ld.d != -1){ ans = Math.max(ans,ld.d+1+rh); depth.d = ld.d+1; } else if(rd.d != -1){ ans = Math.max(ans,rd.d+1+lh); depth.d = rd.d+1; } if(root.data == target){ depth.d = 0; ans = Math.max(lh, rh); } return Math.max(lh,rh)+1; }

[@subhankarpal2800]

Sir I did this code on GFG Practice ,I understand whole logic after that I tried by my own but many times I got different result but now I wrote code as same as in your video but now still got different and , did not run any test case please help me sir , This is the Code Output --------------------------------------- 1 2 3 4 5 N 6 N N 7 8 N 9 10 11 N N N 12 N N N 13 8 Your Output: 8 Expected Output: 7 Main code ----------------------- static class Depth{ int d; public Depth(int d){ this.d = d; } } public static int minTime(Node root, int target) { // Your code goes here Depth depth = new Depth(-1); burn(root,target,depth); return ans; } static int ans = -1; public static int burn(Node root,int target,Depth depth){ if(root == null)return 0; if(root.data == target){ depth.d = 1; return 1; } Depth ld = new Depth(-1); Depth rd = new Depth(-1); int lh = burn(root.left,target,ld); int rh = burn(root.right,target,rd); if(ld.d != -1){ ans = Math.max(ans,ld.d+1+rh); depth.d = ld.d+1; } else if(rd.d != -1){ ans = Math.max(ans,rd.d+1+lh); depth.d = rd.d+1; } return Math.max(lh,rh)+1; }

[@anuj2194]

same bro

[@GxG_Glory]

Same :"(

[@mrsmurf911]

@@GxG_Glory This approach will work only if we start to burn form the leaf node

[@subhankarpal2800]

Sir I did this code on GFG Practice ,I understand whole logic after that I tried by my own but many times I got different result but now I wrote code as same as in your video but now still got different and , did not run any test case please help me sir , This is the Code Output --------------------------------------- 1 2 3 4 5 N 6 N N 7 8 N 9 10 11 N N N 12 N N N 13 8 Your Output: 8 Expected Output: 7 Main code ----------------------- static class Depth{ int d; public Depth(int d){ this.d = d; } } public static int minTime(Node root, int target) { // Your code goes here Depth depth = new Depth(-1); burn(root,target,depth); return ans; } static int ans = -1; public static int burn(Node root,int target,Depth depth){ if(root == null)return 0; if(root.data == target){ depth.d = 1; return 1; } Depth ld = new Depth(-1); Depth rd = new Depth(-1); int lh = burn(root.left,target,ld); int rh = burn(root.right,target,rd); if(ld.d != -1){ ans = Math.max(ans,ld.d+1+rh); depth.d = ld.d+1; } else if(rd.d != -1){ ans = Math.max(ans,rd.d+1+lh); depth.d = rd.d+1; } return Math.max(lh,rh)+1; }

[@prateekgaur2709]

if(root.data == target){ depth.d = 1; //change it to 0; return 1; } 2 test case will run. But 3rd one wont.Because this code is fine only for when leaf node is burnt first.