L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java
Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements
Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements
Пікірлер: 233
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
2 ай бұрын
Yes, was just gonna point that out. Thanks man.
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
8 ай бұрын
Arey but iss me ,when previous becomes 7, how did node changed to 6 again
@priyanshkumar_iitd
5 ай бұрын
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).
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.
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.
How it is possible for you man! You always come up with such blowing solutions.
@vrushabh_kulye7060
2 жыл бұрын
This solutions are already available on internet... btw great explanations....
@ashwinurewar5006
2 жыл бұрын
Gfg pe avlble hai with same eg
@sastashroud7646
2 жыл бұрын
Isn't this available on internet ?
@chandantaneja6388
2 жыл бұрын
@@vrushabh_kulye7060 yeah but nothing can beat his explanation skills.
@mugambo5505
2 жыл бұрын
solution har jagah hai internet par magar solution samjhana mei striver bhai ka koi takkar nhi hai except Harry bhai. fan of both ❤❤❤❤❤❤❤
I've referred to so many channels over my lifetime, ngl...this guy is just GOAT.
In morris traversal code there is a small correction I think There should be curr->left = NULL; After, curr->right = curr->left;
@krishnarajs929
2 жыл бұрын
yesss
@k_harivardhan_4096
2 жыл бұрын
yes @pranjal bansal In java it will look like this curr.left=null;
@parthadhikari8675
Жыл бұрын
Right
You have arranged this playlist series in best order. It is really very helpful.
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.
all 3 approaches are owsome!!!! and the 3rd one using linked list blows up...superbbbbbbbbbbb
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
3 ай бұрын
yeah kudos to you also lest keep growing with bst, graphs and dp
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; } } } }
did it with morris traversal even before watching the video. you taught us so good!
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.
Excellent Explanation, Thank you Striver
literally never thought we could do this question so easily!! i am blown! that too with 3 simple approaches!
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
4 ай бұрын
Thanks bhai
Understood.........Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
in the third approch there should be the curr.left=null after the curr.right=curr.left
@daman666100
2 жыл бұрын
yes, good catch!
What a great explanation bro listening to your explanation reduces my repetitive writing task to remember effectively.
the 2nd solution is perfect for interview and very intuitive.
Mind Blowing Explanation ...hats off :)
Awesome!
Stack Solution can also be implemented with a Queue. Just push Left and then Right instead of Right and then Left.
Thank you so much sir for such a clear and detailed explanation !
What a gem !!
Salute to your efforts for making such a wonderful series.
Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.
Thank You Striver so much, after watching all the previous binary trees videos, i could do this question without watching the solution!!
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.
thank you
What a solid explanation man! Thanks!
Great explanation. Very nicely explained.
Thank you Bhaiya
I must say this is a well crafted question. THANKS
whenever I face a problem in solving a problem, first choice is TUF.. ]THANKS FOR MAKING THIS VIDEO.
The first approach is really amazing 👏👏👏
awesome...
understood , great content, preparing for interview from it
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
one more thing, cur->left = nullptr; before starting iteration over next cur because it might give some kind of error
bow down ! recursion is really crazy and beautiful.
I loved the stack approach !
Keep uploading videos keep going Thank you for this amazing contents .
Just Wow Striver Bhaiya.......Conceptual videos are the best,code excluded.
Nice
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
In the last approach after cur->right= cur->left ; then cur->left=NULL should be there.
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 .
That evil okayyy at 7:25 lol, funny!
understand this question very easily thanks
Nice solution!! Thanks for making! Morris travesal solution starts at 15:42 !!!
Was able to code it myself after watching the previous morris traversal video :)
Awesome explanation 🔥🔥🔥
understooooood well. thanks :)
kya padhate ho bhai, thank you so much for the quality content!
how beutiful the first approach...
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.
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?
Awesome explanation 🙏
Niceeee
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
17 күн бұрын
What are you doing now? Unemployed or student or employed
@sauravchandra10
17 күн бұрын
@@Anonymous____________A721 Employed
@Anonymous____________A721
16 күн бұрын
@@sauravchandra10 wow that's grear
understood
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
2 жыл бұрын
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
2 жыл бұрын
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
Very Good Explanation bruh!
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; }
Superb and thanks a lot bhaiya ❤️
Understood! BTW, I have created a PR with Java code for this problem. Do give it a check!
@takeUforward
2 жыл бұрын
Merged, thanks.
🔥🔥
Huge Respect...❤👏
at 17:30 bro, you need to add cur->left = null as well.
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; }
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
2 жыл бұрын
Do a dry run, you will see its done.
@krishnarajs929
2 жыл бұрын
Yes you need to change that curr->right = curr->left; then curr->left = NULL
Maza aaya! Understood ;)
Mind blowing explaination
In morris traversal method, u didn't make current's left pointer null
Amazing. Keep making videos. You are really teaching us a lot!!
Can someone please tell that if we are prohibited to use auxiliary data structure then can we use recursion or not ???
I like stack approach 🧡🧡
absolute genius!!
Freaking loved this video!!!
one word only (woow!)🙌
What will happen if prev is inside the flatten function?
extremely perfect
in first approach isnt it reverse preorder and not reverse postorder?
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
9 ай бұрын
It's because each recursion call takes O(1) stack space internally. So for N number space complexity is O(N).
Striver you forgot to alter the left links for all nodes :)
thanks
can't we use dummy node to create linked list?
Please teach us how to develop a thought process to come up with these kind of solutions.
@xd9050
Жыл бұрын
practice
Thankyou sir
I could get the last algo on my own and felt so satisfied seeing Striver told the same method.
best lectures on tree.
Thanks good job
DONE :)
Thank you
Best Solution
Thank you sir
Great Sir