L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java

[@Jai_Jai_shri_Ram108]

in 3rd approach please add this line curr->left=NULL in the if block, after curr->right=curr->left; if you don't it give run time error:

[@prathamsharma4416]

thanks mate

[@kingmaker9082]

Nice

[@AjayThakur-lo3cl]

Thanks buddy :)

[@U2011-n7w]

thanks bro

[@keshavbiyani9202]

Yes, was just gonna point that out. Thanks man.

[@vedantsharma5876]

This series is not best just because of the quality content, but also the way Striver has organized this playlist. The previous video was Morris Traversal, and this is the application of the Morris Traversal. You definitely are a gem Striver ❤

[@naveen9646]

same for time to burn the tree prob which requires prerequiste of count nodes at distance k prob

[@saimanaspathapadu1299]

Arey but iss me ,when previous becomes 7, how did node changed to 6 again

[@priyanshkumar17]

Yes, when I watched the burn binary tree problem & saw the way it was solved using the previous problem, my concepts became stronger.@@naveen9646

[@rushidesai2836]

@@saimanaspathapadu1299 6 ka right and left recursive call complete hua, uske baad 6 ka right set kiya as 7(prev), and 6 ka left as null. Finally, prev(last visited node) is set as 6(which is current node).

[@samridhshubham8109]

I've referred to so many channels over my lifetime, ngl...this guy is just GOAT.

[@RishiMishra1997]

Your video lectures are very good and I am really thankful that you are providing us the free content. I think you forgot in the last pseudocode(approach 3) cur->left=NULL and due to that some of the viewers may have the confusion that's why I am writing this comment. Node *cur=root, *prev=NULL; while(cur!=NULL){ if(cur->left!=NULL){ prev=cur->left; while(prev->right){ prev=prev->right; } prev->right=cur->right; cur->right=cur->left; cur->left=NULL; //this line } cur=cur->right; } And thanks again for such quality content. Edit :- Some of the viewers has already wrote this in the comment and code which you gave is also correct.

[@pulkitchausali1354]

One of the best explanation from striver In Approach 3 after if block ends add one line cur.left = null; otherwise output will be wrong as left pointer is pointing to its original left child

[@khalidalam980]

Thanks bhai

[@rishabhkumar8115]

all 3 approaches are owsome!!!! and the 3rd one using linked list blows up...superbbbbbbbbbbb all 3 approaches are owsome!!!! and the 3rd one using linked list blows up...superbbbbbbbbbbb

[@Dontpushyour_luck]

did it with morris traversal even before watching the video. you taught us so good!

[@SuyashSoni248]

Can be done by IBH(Induction-Base-Hypthesis) - def flatten(self, root): if root is None: return self.flatten(root.left) self.flatten(root.right) rL, rR = root.left, root.right root.left = None root.right = rL # induction temp = root while temp and temp.right: temp = temp.right temp.right = rR

[@deepaksarvepalli2344]

How it is possible for you man! You always come up with such blowing solutions.

[@vrushabh_kulye7060]

This solutions are already available on internet... btw great explanations....

[@ashwinurewar5006]

Gfg pe avlble hai with same eg

[@sastashroud7646]

Isn't this available on internet ?

[@chandantaneja6388]

@@vrushabh_kulye7060 yeah but nothing can beat his explanation skills.

[@mugambo5505]

solution har jagah hai internet par magar solution samjhana mei striver bhai ka koi takkar nhi hai except Harry bhai. fan of both ❤❤❤❤❤❤❤

[@pranjalbansal8459]

In morris traversal code there is a small correction I think There should be curr->left = NULL; After, curr->right = curr->left;

[@krishnarajs929]

yesss

[@k_harivardhan_4096]

yes @pranjal bansal In java it will look like this curr.left=null;

[@parthadhikari8675]

Right

[@sameekshamurdia5-yeariddph649]

Congrats guys for completing Binary Trees, ab BST start krte h 🥳🥳 Thank you so much striver bhaiya for the amazing series💖

[@teqarine5752]

oof

[@arshmehta50]

Which yr

[@aastikofficial6100]

yeah kudos to you also lest keep growing with bst, graphs and dp

[@ANANDKUMAR-jk9yp]

Striver Bhaiya, the same question was asked in my DE Shaw Interview. Unfortunately, couldn't answer that. Kaash , pahle dekh liya hota aapka yeh video. Anyways, thank you for your amazing explanation.

[@karthik-varma-1579]

Congratulations, For Compeletion of Tree Ka Series

[@stith_pragya]

Understood.........Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@abdulmoizasif3930]

The first solution was absolutely beautiful.

[@sparshsharma6068]

Amazing explanation bhaiya! Just one doubt, I think while recording, you forgot to set the left pointers of nodes to null in morris traversal. Edit: The code links in the description are 100% working and correct.

[@jaditi930]

This is what passion speaks like.Gets straight to the heart.I was finding hard to understand this concept.Thankyou so much Finally found someone to get the intuition behind algos.This is the first video of yours and subscribed right away.Just keep going.

[@amitupadhyay2445]

in the third approch there should be the curr.left=null after the curr.right=curr.left

[@daman666100]

yes, good catch!

[@ajayagrawal2067]

the 2nd solution is perfect for interview and very intuitive.

[@satakshipal5008]

You have arranged this playlist series in best order. It is really very helpful.

[@deanwinchester8691]

cur->left should be set to NULL or else it won't change and will be not accepted as in the question it is told that the nodes in flatten BT must be set to NULL.

[@pawanlok1776]

whenever I face a problem in solving a problem, first choice is TUF.. ]THANKS FOR MAKING THIS VIDEO.

[@spandanrastogi7144]

Stack Solution can also be implemented with a Queue. Just push Left and then Right instead of Right and then Left.

[@alesblaze4745]

bro after watching your previous videos from this tree series and til 2:16 only i watched this video, i was able to come up with an approach and solved it iteratively. thanks a lot. Code : class Solution { public void flatten(TreeNode root) { TreeNode temp = root; if(temp == null) return; Deque stack = new LinkedList(); while(temp != null || !stack.isEmpty()) { TreeNode prev = null; while(temp != null) { if(temp.right != null) { stack.push(temp.right); } temp.right = temp.left; temp.left = null; prev = temp; temp = temp.right; } if(!stack.isEmpty()) { TreeNode nextRight = stack.pop(); prev.right = nextRight; temp = nextRight; } } } }

[@iamnottech8918]

The main Intution for last approach is if we use normal Morris then we will loose right pointer and if we make it to root->right then a connection is made it will be not lost and also it is at its correct position

[@rishabhkumar8115]

all 3 approaches are owsome!!!! and the 3rd one using linked list blows up...superbbbbbbbbbbb

[@codding32world50]

why to spam nonsense write once only.. it keeps imp discussion down

[@AdityaMehta1307]

Excellent Explanation, Thank you Striver

[@shivangisrivastava1158]

literally never thought we could do this question so easily!! i am blown! that too with 3 simple approaches!

[@abhaykumarsingh3884]

Thank you striver I have figure out morris approach before even watching video But yes it took me 1:5 hr to come to actual solution But i think recursive soln is more hard

[@dsa_tutorial]

Guys something missing in 3rd approach after writing prev->right = curr->right curr->right = curr->left curr->left = NULL please include this line in order to break previous connections .

[@PiyushKumar-mn3uh]

Guys, There are something missing in 3rd approach. After this line curr->right = crr->left add curr->left = NULL to break the prev connections of left O.W you will get run time error.

[@pulkitjain5159]

this reccursion will also work , normal preorder traversal, this will also take O(N) time Node * flattenMe(Node * root){ if(root == nullptr) return nullptr; Node * leftSubtreeLinkedList = flattenMe(root->left); Node * rightSubtreeLinkedList = flattenMe(root->right); root->left = nullptr; root->right = leftSubtreeLinkedList; Node * ptr = root; while(ptr->right!=nullptr){ ptr = ptr->right; } ptr->right = rightSubtreeLinkedList; return root; }

[@codding32world50]

how beutiful the first approach...

[@eshandhok2591]

one more thing, cur->left = nullptr; before starting iteration over next cur because it might give some kind of error

[@apmotivationakashparmar722]

Thank you So much Striver !

[@himanshugupta7010]

In the last approach after cur->right= cur->left ; then cur->left=NULL should be there.

[@PrinceKumar-el7ob]

bow down ! recursion is really crazy and beautiful.

[@bommidinitin]

beautiful explanation

[@WhisperingWalnuts]

Nice solution!! Thanks for making! Morris travesal solution starts at 15:42 !!!

[@sauravchandra10]

Was able to complete the binary tree series in 5 days, looking to wrap up the BST questions in the next 2-3 days.

[@Anonymous____________A721]

What are you doing now? Unemployed or student or employed

[@sauravchandra10]

@@Anonymous____________A721 Employed

[@Anonymous____________A721]

@@sauravchandra10 wow that's grear

[@vedantnaikwadi5394]

@@sauravchandra10 bro which comapany any tips for interviews and aptitude??

[@sauravchandra10]

@@vedantnaikwadi5394 turing, do DSA + Dev or ML and also focus on OOPS.

[@sujan_kumar_mitra]

Understood! BTW, I have created a PR with Java code for this problem. Do give it a check!

[@takeUforward]

Merged, thanks.

[@ANANDKUMAR-jk9yp]

Sir, in the third approach (20:52), you are saying that you are finding the rightmost guy in the left subtree. But, initializing prev=cur->left and using the while loop may not always work. For ex: 1 / \ 2 4 / 3 In this case, if we are at the root then the last guy in the preorder traversal of left subtree according to your algorithm will be 2 , although it should be 3. Plz correct me, if i am wrong. Although, your algorithm works on even these cases well.

[@anshumansharma4580]

Yes it should be 2. Therefore 2's right will point to 4(see the code again). We will set right child of node 1 to node 2. Now we will move cur from 1 to 2. Now at node 2, what is the "rightmost guy in left sub-tree"? It is node 3. Now we will set right child of node 3 to right child of cur ; i.e right child of node2 which is 4. That's how your question is answered. Cheers !! Ask if you have any doubt.

[@ShivamKumar-hf5ec]

if the left part of curr contains only one node itself so its left is null then the prev will automatically point to curr and will not point something else

[@rajrajesh1669]

In the 3rd approach i think there is an issue, we are going as right as possible, but what if the right most node has a left child?

[@saicharan4669]

The first approach is really amazing 👏👏👏

[@LalX77]

Thank You Striver so much, after watching all the previous binary trees videos, i could do this question without watching the solution!!

[@dheerajsharma5492]

I must say this is a well crafted question. THANKS

[@alesblaze4745]

at 17:30 bro, you need to add cur->left = null as well.

[@nikhilprasad644]

easy java Solution: Self explanatory: Just consider for 1 node, rest happens automatically class Solution { public void flatten(TreeNode root) { solve(root); } TreeNode solve(TreeNode root){ if(root==null) return root; if(root.left==null && root.right==null) return root; TreeNode r=root.right; TreeNode l=root.left; root.left=null; root.right=solve(l); TreeNode p=root; while(p.right!=null){ p=p.right; } p.right=solve(r); return root; } }

[@yashwagh83]

That evil okayyy at 7:25 lol, funny!

[@iamnottech8918]

approach 3 void flatten(TreeNode* root) { while(root!=NULL) { if(root->left!=NULL) { TreeNode*temp=root->left; while(temp->right!=NULL) //that one condition to break that link is now not required . { temp=temp->right; } temp->right=root->right; //smart play root->right instead of root made connection for future root->right=root->left ; root->left=NULL; } root=root->right; } } };

[@anshulgoel1940]

Two pointer approach in Kotlin fun flattenTree(head: Node?): Node?{ var p = head var q = head while(p != null){ if(p!!.left != null){ q = p!!.left while(q!!.right != null){ q = q!!.right } q!!.right = p!!.right p!!.right = p!!.left p!!.left = null } else { p = p!!.right } } return head }

[@rahulsrivastava1040]

Mind Blowing Explanation ...hats off :)

[@ankitshukla8972]

In the last approac , using Morris traversal , you forgot to put curr.left= null . TreeNode curr=root; while(curr!=null){ if(curr.left != null){ TreeNode prev=curr.left; while(prev.right != null){ prev=prev.right; } prev.right=curr.right; curr.right=curr.left; curr.left=null; } curr=curr.right; }

[@ketonesgaming1121]

What a gem !!

[@kirubakaran1547]

In morris traversal method, u didn't make current's left pointer null

[@adrishsaha407]

Just Wow Striver Bhaiya.......Conceptual videos are the best,code excluded.

[@toxic_roy]

here's the 3rd approach(with correction): void flatten(Node *root) { //code here Node* curr = root; while(curr!=NULL){ if(curr->left!=NULL){ Node* prev = curr->left; while(prev->right){ prev=prev->right; } prev->right=curr->right; curr->right = curr->left; curr->left=NULL; } curr=curr->right; } }

[@pritishpattnaik4674]

I loved the stack approach !

[@AditiAgarwal-rw3lq]

Striver you forgot to alter the left links for all nodes :)

[@chaitanyakrishna9398]

What a great explanation bro listening to your explanation reduces my repetitive writing task to remember effectively.

[@aryansinha1818]

16:00 Using Morris Traversal

[@sauravdutta]

Was able to code it myself after watching the previous morris traversal video :)

[@icongrindsetsfj]

Please teach us how to develop a thought process to come up with these kind of solutions.

[@xd9050]

practice

[@AngadSingh97]

kya padhate ho bhai, thank you so much for the quality content!

[@OmPrakash-kb2wq]

best lectures on tree.

[@bhavikasodagum1121]

missed cur->left=NULL, then it will worl

[@harshdasila6680]

CODE: //small correction in morris traversal to assign curr->left = NULL class Solution { public: void f(TreeNode* curr){ TreeNode* prev=NULL; while(curr!=NULL) { if(curr->left!=NULL){ prev = curr->left; while(prev->right){ prev = prev->right; } prev->right = curr->right; curr->right = curr->left; curr->left = NULL; } curr = curr->right; } } void flatten(TreeNode* root) { f(root); }

[@yashgarg8906]

In the morris traversal approach, shouldn't we make the curr->left = NULL ? Because after doing curr->right = curr->left Curr is having same subtrees on both left and right so shouldn't we remove the left subtree?

[@takeUforward]

Do a dry run, you will see its done.

[@krishnarajs929]

Yes you need to change that curr->right = curr->left; then curr->left = NULL

[@vaalarivan_p]

16:00 - 17:15 dna 20:51(edoc)

[@codingp110]

Awesome!

[@Learnprogramming-q7f]

Thank you Bhaiya

[@Mathaan-i4j]

Very Good Explanation bruh!

[@Shivi32590]

thank you

[@ashishverma1382]

understand this question very easily thanks

[@mayanksingh5783]

Mind blowing explaination

[@dsa_tutorial]

Keep uploading videos keep going Thank you for this amazing contents .

[@prithvigupta8215]

15:25 Morris Traversal

[@harshitbalodi9423]

' ' ' ' ' ' ' ' void flatten(TreeNode* root) { TreeNode*cur=root; while(cur!=NULL){ if(cur->left!=NULL){ TreeNode*prev=cur->left; while(prev->right) prev=prev->right; prev->right=cur->right; cur->right=cur->left; cur->left=NULL; } cur=cur->right; } }

[@we_crood]

solve this within 20 mins on my own thank you

[@pthegreat1104]

how do u approach man, I am finding things after morris traversal to be quite tough

[@anmolverma075]

​@@pthegreat1104 true ,same for me. Going straight above my head.

[@Piyush-h3b4k]

Method 3: correction: // method 3: t.=O(n) s.c=O(1) TreeNode* curr=root; while(curr) { if(curr->left) { TreeNode* temp=curr->left; while(temp->right) temp=temp->right; temp->right=curr->right; curr->right=curr->left; curr->left=NULL; } curr=curr->right;

[@ankitpalsingh8191]

awesome...

[@m4rk509]

In the first method how space complexity is O(N)...we've not made any extra ds...is this because of stack size due to function calls?

[@shubham_v]

It's because each recursion call takes O(1) stack space internally. So for N number space complexity is O(N).

[@anujrawat6304]

understood , great content, preparing for interview from it

[@mohdkhaleeq7468]

in appraoch 1 it would be reverse preorder

[@avanishmaurya2034]

Nice

[@shivangisrivastava1158]

Salute to your efforts for making such a wonderful series.

[@cupidchakma6448]

can striver please provide a way to debug and visualize recursive problems, its hard to visual and imagine what will happen on next step when doing recursion related problems

[@nayanikasinghachowdhury6747]

in first approach isnt it reverse preorder and not reverse postorder?

[@mohammedadnan2450]

Bhaiya its better to solve this with morris traversal concept

[@imilanprj]

Awesome explanation 🔥🔥🔥

[@motabhaimotivation]

I could get the last algo on my own and felt so satisfied seeing Striver told the same method.

[@UECAshutoshKumar]

Thank you sir

[@abhinavaarya9437]

5:48 Seven! Seven! Monica vibes

[@ShubhamKumar-ex3nk]

can't we use dummy node to create linked list?

[@YeaOhYeahh]

🔥🔥

[@Jashan77114]

how S for 1st approach is O(n) and for third approach is O(1) ?

[@xd9050]

did u get its answer

[@Anythiny]

recursion stack space

[@techxpertrishabh7011]

I like stack approach 🧡🧡

[@jatinsingh1368]

Best Approach : CODE : void flatten(TreeNode* root) { //head and tail are passed by reference TreeNode* head = NULL,*tail=NULL; find(root,head,tail); } void find(TreeNode* root,TreeNode*& head,TreeNode*& tail) { if(root==NULL) return; TreeNode* left1 = root->left; TreeNode* right1 = root->right; if(head==NULL) { head=root; tail=root; // keep care to make left NULL , else will create problem tail->left=NULL; } else { tail->right=root; // keep care to make left NULL , else will create problem root->left=NULL; tail=root; } find(left1,head,tail); find(right1,head,tail); }

[@paragroy5359]

Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.

[@shreyasingh7833]

Thank you so much sir for such a clear and detailed explanation !