L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java
ฝัง
- เผยแพร่เมื่อ 31 ส.ค. 2021
- Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements
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:
thanks mate
Nice
Thanks buddy :)
thanks bro
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 ❤
same for time to burn the tree prob which requires prerequiste of count nodes at distance k prob
Arey but iss me ,when previous becomes 7, how did node changed to 6 again
Yes, when I watched the burn binary tree problem & saw the way it was solved using the previous problem, my concepts became stronger.@@naveen9646
@@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).
How it is possible for you man! You always come up with such blowing solutions.
This solutions are already available on internet... btw great explanations....
Gfg pe avlble hai with same eg
Isn't this available on internet ?
@@vrushabh_kulye7060 yeah but nothing can beat his explanation skills.
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.
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.
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.
Congrats guys for completing Binary Trees, ab BST start krte h 🥳🥳
Thank you so much striver bhaiya for the amazing series💖
oof
Which yr
yeah kudos to you also lest keep growing with bst, graphs and dp
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.
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.
all 3 approaches are owsome!!!! and the 3rd one using linked list blows up...superbbbbbbbbbbb
You have arranged this playlist series in best order. It is really very helpful.
In morris traversal code there is a small correction I think
There should be
curr->left = NULL;
After, curr->right = curr->left;
yesss
yes @pranjal bansal
In java it will look like this
curr.left=null;
Right
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
Thanks bhai
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
did it with morris traversal even before watching the video. you taught us so good!
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;
}
}
}
}
literally never thought we could do this question so easily!! i am blown! that too with 3 simple approaches!
Understood.........Thank You So Much for this wonderful video.............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Excellent Explanation, Thank you Striver
What a great explanation bro listening to your explanation reduces my repetitive writing task to remember effectively.
Thank you so much sir for such a clear and detailed explanation !
the 2nd solution is perfect for interview and very intuitive.
whenever I face a problem in solving a problem, first choice is TUF..
]THANKS FOR MAKING THIS VIDEO.
in the third approch there should be the
curr.left=null
after the curr.right=curr.left
yes, good catch!
Salute to your efforts for making such a wonderful series.
Thank You Striver so much, after watching all the previous binary trees videos, i could do this question without watching the solution!!
Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.
Mind Blowing Explanation ...hats off :)
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
I must say this is a well crafted question. THANKS
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.
The first approach is really amazing 👏👏👏
Stack Solution can also be implemented with a Queue. Just push Left and then Right instead of Right and then Left.
That evil okayyy at 7:25 lol, funny!
Awesome!
understood , great content, preparing for interview from it
how beutiful the first approach...
bow down !
recursion is really crazy and beautiful.
Great explanation. Very nicely explained.
What a solid explanation man! Thanks!
Thank you Bhaiya
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
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 .
What a gem !!
awesome...
kya padhate ho bhai, thank you so much for the quality content!
I loved the stack approach !
one more thing, cur->left = nullptr; before starting iteration over next cur because it might give some kind of error
Keep uploading videos keep going Thank you for this amazing contents .
Was able to code it myself after watching the previous morris traversal video :)
Just Wow Striver Bhaiya.......Conceptual videos are the best,code excluded.
Was able to complete the binary tree series in 5 days, looking to wrap up the BST questions in the next 2-3 days.
What are you doing now?
Unemployed or student or employed
@@Anonymous____________A721 Employed
@@sauravchandra10 wow that's grear
Nice solution!! Thanks for making! Morris travesal solution starts at 15:42 !!!
understand this question very easily
thanks
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.
thank you
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?
In the last approach after cur->right= cur->left ; then cur->left=NULL should be there.
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 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;
}
Understood!
BTW, I have created a PR with Java code for this problem. Do give it a check!
Merged, thanks.
Nice
Awesome explanation 🔥🔥🔥
at 17:30 bro, you need to add cur->left = null as well.
best lectures on tree.
Please teach us how to develop a thought process to come up with these kind of solutions.
practice
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.
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.
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
Amazing. Keep making videos. You are really teaching us a lot!!
Superb and thanks a lot bhaiya ❤️
understooooood well. thanks :)
Very Good Explanation bruh!
I could get the last algo on my own and felt so satisfied seeing Striver told the same method.
Niceeee
Awesome explanation 🙏
Maza aaya! Understood ;)
understood
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
}
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;
}
}
In morris traversal method, u didn't make current's left pointer null
Mind blowing explaination
🔥🔥
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?
Do a dry run, you will see its done.
Yes you need to change that curr->right = curr->left; then curr->left = NULL
Striver you forgot to alter the left links for all nodes :)
solve this within 20 mins on my own thank you
how do u approach man, I am finding things after morris traversal to be quite tough
@@pthegreat1104 true ,same for me.
Going straight above my head.
I like stack approach 🧡🧡
one word only (woow!)🙌
Huge Respect...❤👏
Can someone please tell that if we are prohibited to use auxiliary data structure then can we use recursion or not ???
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?
It's because each recursion call takes O(1) stack space internally. So for N number space complexity is O(N).
in first approach isnt it reverse preorder and not reverse postorder?
What will happen if prev is inside the flatten function?
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;
}
}
absolute genius!!
15:25 Morris Traversal
Firstly thanks striver , anyone tell me why the recursive approach will have sc=O(n) , it should be O(1) .
Its the function call stack memory..
How about this solution
*/
class Solution {
public:
TreeNode* dfs(TreeNode *root){
if(root == NULL){
return NULL;
}
TreeNode *left = dfs(root->left);
TreeNode *right = dfs(root->right);
TreeNode *node = root;
node->right = left;
while(node->right != NULL){
node = node->right;
}
node->right = right;
root->left = NULL;
return root;
}
void flatten(TreeNode* root) {
root = dfs(root);
}
Bhaiya its better to solve this with morris traversal concept
Striver you are just awesome
'
'
'
'
'
'
'
'
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;
}
}
can't we use dummy node to create linked list?