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).

[@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.

[@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.

[@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 ❤❤❤❤❤❤❤

[@samridhshubham8109]

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

[@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

[@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.

[@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

[@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.

[@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

[@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

[@rishabhkumar8115]

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

[@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.

[@Dontpushyour_luck]

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

[@stith_pragya]

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

[@karthik-varma-1579]

Congratulations, For Compeletion of Tree Ka Series

[@amitupadhyay2445]

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

[@daman666100]

yes, good catch!

[@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

[@spandanrastogi7144]

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

[@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

[@ajayagrawal2067]

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

[@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; } } } }

[@shivangisrivastava1158]

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

[@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

[@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

[@eshandhok2591]

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

[@AdityaMehta1307]

Excellent Explanation, Thank you Striver

[@bommidinitin]

beautiful explanation

[@pawanlok1776]

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

[@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?

[@himanshugupta7010]

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

[@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.

[@codding32world50]

how beutiful the first approach...

[@PrinceKumar-el7ob]

bow down ! recursion is really crazy and beautiful.

[@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 .

[@LalX77]

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

[@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; }

[@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.

[@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

[@chaitanyakrishna9398]

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

[@saicharan4669]

The first approach is really amazing 👏👏👏

[@kirubakaran1547]

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

[@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; }

[@dheerajsharma5492]

I must say this is a well crafted question. THANKS

[@WhisperingWalnuts]

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

[@sujan_kumar_mitra]

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

[@takeUforward]

Merged, thanks.

[@icongrindsetsfj]

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

[@xd9050]

practice

[@rahulsrivastava1040]

Mind Blowing Explanation ...hats off :)

[@alesblaze4745]

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

[@Shivi32590]

thank you

[@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).

[@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

[@yashwagh83]

That evil okayyy at 7:25 lol, funny!

[@adrishsaha407]

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

[@AditiAgarwal-rw3lq]

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

[@sauravdutta]

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

[@codingp110]

Awesome!

[@Learnprogramming-q7f]

Thank you Bhaiya

[@pritishpattnaik4674]

I loved the stack approach !

[@paragroy5359]

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

[@aryansinha1818]

16:00 Using Morris Traversal

[@ashishverma1382]

understand this question very easily thanks

[@ketonesgaming1121]

What a gem !!

[@anujrawat6304]

understood , great content, preparing for interview from it

[@shreyasingh7833]

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

[@AngadSingh97]

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

[@shivangisrivastava1158]

Salute to your efforts for making such a wonderful series.

[@lucky_raiser]

Firstly thanks striver , anyone tell me why the recursive approach will have sc=O(n) , it should be O(1) .

[@rishigupta4843]

Its the function call stack memory..

[@dsa_tutorial]

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

[@ankitpalsingh8191]

awesome...

[@avanishmaurya2034]

Nice

[@bhargavnagacharan1899]

Bro small correction in the video, before coming out of if statements cur->left= NULL should be there. in the github link it is there but in video it is not there.

[@ankitkr09]

yes in the morris traversal approach.. after prev->right = cur->right; cur->right = cur->left; cur->left = NULL; // Missing

[@nayanikasinghachowdhury6747]

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

[@Mathaan-i4j]

Very Good Explanation bruh!

[@OmPrakash-kb2wq]

best lectures on tree.

[@ShubhamKumar-ex3nk]

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

[@mayanksingh5783]

Mind blowing explaination

[@chiragbansod8252]

understood

[@bhavikasodagum1121]

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

[@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 }

[@mohammedadnan2450]

Bhaiya its better to solve this with morris traversal concept

[@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

[@SWE_69]

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.

[@aadityakhetan956]

Great explanation. Very nicely explained.

[@gauravbansalkec]

How is the space complexity O(n) for the first soln

[@piyushacharya7696]

recursion function calls gets stored in the stack.

[@aryansinha1818]

What will happen if prev is inside the flatten function?

[@sandeepsingh-vo8kd]

How in first method space complexity is 0(n). I think it should be 0(1) becoze we are using only one variable in which we are keep on changing value.... please confirm any one?

[@piyushacharya7696]

Recursion stack space bhool gaye kya bro

[@doingsneakypeakylike]

What a solid explanation man! Thanks!

[@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; } }

[@raghavjha8040]

how the space complexity of second approach is O(n)? Please explain

[@xd9050]

did u get the ans

[@YeaOhYeahh]

🔥🔥

[@mohdkhaleeq7468]

in appraoch 1 it would be reverse preorder

[@prithvigupta8215]

15:25 Morris Traversal

[@imilanprj]

Awesome explanation 🔥🔥🔥

[@MaanyaSekhri1234]

Can someone please tell that if we are prohibited to use auxiliary data structure then can we use recursion or not ???

[@motabhaimotivation]

But can anyone explain how can the time complexity O(n) because it seems as if while finding the rightmost of the prev we would have travelled the nodes in between already which will then again be traversed as cur afterwards. so there are going to be a lot of nodes that are going to traversed twice. i think.

[@AnshulSharma-gq2vn]

One way to think about it is: each node can be visited at most two times, one by the outer while loop and another by the inner while loop. Thus the time complexity will be O(2*n) == O(n).

[@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; } }

[@UECAshutoshKumar]

Thank you sir