Serialize & Deserialize A Binary Tree - Crafting Recursive Solutions To Interview Problems
HTML-код
- Опубликовано: 2 окт 2024
- Code & Problem Statement @ backtobackswe....
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given a root node for a binary tree, serialize the binary tree into a string representation. Deserialize that same string representation into a tree identical to the original tree given.
The key is to understand what our fundamental operation/job is in each call to the function.
Our fundamental job is to encode/materialize a single node/int value.
Compiler Design Phases: www.geeksforge...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
Elements of Programming Interviews problem 10.13
Table of Contents:
The Problem Introduction 0:00 - 0:55
Drawing A Parallel 0:55 - 3:19
Deciding How To Traverse & Encode The Tree 3:19 - 4:05
Let's Begin Crafting .serialize() 4:05 - 4:25
Flashback 4:25 - 7:34
Crafting .deserialize(): How Do We Track State? 7:34 - 12:29
Can You Visualize This In Your Brain? 12:29 - 13:28
That's All 13:28 - 14:19
Wrap Up 14:19 - 14:59
The code for this problem is in the description. Fully commented solely for teaching purposes.
Great video! Thank you a lot!
Really liked how you described step-by-step thinking, including incorrect direction and small tips (like a queue).
Also, noticed a mistake on deserialization code:
ruclips.net/video/suj1ro8TIVY/видео.html
Both pointers point to the left node, instead of left and right.
ok
When Im stuck on a problem I say a silent prayer that BackToBack SWE has covered it on video
lmao
that is so true
💯
Lmao this is so accurate!
😂LMAO
This world needs a teacher like you. I would suggest that you do a full time teacher and teach the next generation on how to approach the problem and think about the solution.
ye- we shall see what i do
Pls come back, you'll get this channel to 10 million ,who cares about 100k. Anyways hope ur doing good and ur one of the best teachers I've ever known!!
thx Bro
nice!!
ممكن اعرف ايه المصادر اللي درستها للمقابله
@@lilley2595 Indeed.
@@lilley2595
Before the interview I started revising some object oriented programming from GeeksForGeeks, then I solved some SQL problems from HackerRank.
Regarding Data structures and Algorithms u need to revise the main concepts like: linear data structures, trees, graphs and sorting. watch Back To Back SWE videos it's so simple, then you can do more practice on leetcode!
I like it when the codes just pop out when you are coming out with the idea
ye, is' magic
You are absolutely amazing. I have been going through several DS/Algo tutorials but the effort you put in making things simple and understandable is simply remarkable. At this moment, what's the deficit between the contents of your course vs the contents available in this channel?
The course will be me posting materials (2-4 videos a week) and all my technical content will be there for the next 6 months or so. I'm posting more often, in more detail, & helping students in the fb group
I really liked that you also explained mental barriers like this. I appreciate it.
haha nice
Your first null check in serialise is very important. I missed the delimiter while returning X and spent time finding what was wrong. So X, is very important:)
One of the best explanation. One request, please make a video on "How to picturise a recursion solution". Recursive solution are easy when you see them,but to think of those solution by yourself is not that easy. Thanks in advance
ok
Its already 99.5k, dude u r close to 100k subs. Keep up the good work, well deserved!
Yeah, what a ride. The internet is to be thanked.
@@BackToBackSWE Ben, just a suggestion for your later videos, explain iterative solution also. I did this question with recursion and level order traversal, that way you can teach more than one concept in a question.
Ben, your explanations are amazing! Every time I get stuck doing a problem, I just pray that you have a video on how to solve it because none of the other RUclips videos stick as well as yours do. Thank you so much for this!
hahaha nice, well glad to head that
+1
Thanks a lot for the video! I am still confused by one thing, there is leetcode questions like "Construct Binary Tree from Inorder and Postorder Traversal", which means you need two serialized data array (inorder and postorder) to decide how a tree is built right? Could you please explain a bit on this? Thank you!
The difference here is that we add extra "nulls" when generating the order, allowing each tree we rebuild later on is unique. In the problem you said, there is no "null" in there, thus we need 2 orders to build the tree. For example, with preorder [1,2,3], there may be some trees that can be reconstructed, but if we add "null" to have a preorder of [1,2,3, null, null, null, null], we can only build a unique tree.
I would be very interested in seeing you do a mock interview through one of these videos. Maybe grab a friend and interview each other and see how that pans out for content
Yeah haha, Ive though of this and may do a few this Fall. I'm launching a course & will shift all my focused teaching there and may get more creative here on the channel.
Really good explanation.
A bit confused, the serialize function, is it really a pre-order? As I see after returning from a node we are appending the left and right value to the root. It's the way you are returning that that looks like pre-order String. But instead, it is post-order traversal, right?
Below is the per-order to return same string as yours:
private void serializeHelper(TreeNode root, StringBuilder sb){
if(root == null){
sb.append("X,");
return;
}
sb.append(root.val).append(",");
serialize(root.left, sb);
serialize(root.right, sb);
}
I don't remember the code tbh - I'd answer if I did but fast replying to comments
Man, you might not the best in technical problem, but you must the be the best to articulate them! Great job. I hope(and i believe!) you can go a long way in any big name company or may become a professor in college.
ye
Superb explanation, thankyou so much
sure
You forgot to mention postorder. In languages like Rust postorder can be cleaner solution due to ownership/borrowing model. Btw could be nice if you also provide optimisation for this solution to make serialised string more compact.
thanks
Great Explanation. I understood the concept very well.
Thank You so much for the series of videos, it really helps a lot.
Just a small correction in the serialize method - Just add extra separator "," after the leftSubtree as well.
While returning, make the change in the code as: return root.val + "," + leftSubtree + "," + rightSubtree;
Because if you don't add the extra "," and try to solve the leet code problem, it will give you the error for bad input String "XX3" as it won't be able to deserialize it to Integer value while creating the node.
thanks
Hey! Thanks a ton for this video!
Also, I was wondering whether we could use the level order traversal to serialize our tree?
we Could . i mean yeah once we get the level, we dont know the parent of the level. we could try accessing thru smart indexing . lets say level x has 2 values. then level x+1 will have 4.
[1]
[2,3]
[4,5,6,7]
so if we are on level 2, we have 2 on index 0 and 3 on index 1.
the children of 2(index 0) would be 0*2+0(0) and 0*2+1(1)
the children of 3(index 1) would be 1*2+0(2) and 1*2+1(3).
this could be a way to store. but becuase its a 2d array structure, i think a single q would be better altho the space would be same as every node appears once only.
Yes you can
What will you say if the interviewer asks you that why use PreOrder why not BFS or inorder? What are we supposed to answer?
The deserialization depends on the serialization. Any can work
I see thank you
At first I used complex serialization with braces and commas and had to write my own string generator and parser. I also used index tracking when decoding.
The code worked, but the performance was abysmal!
Turns out that all of this could be avoided:
- A comma for separation is enough for serialization,
- str.split(',') is enough to turn the string into a list of tokens for de-serialization, and
- deque(tokens) is great to hold the values. Left-popping the deque does away with the index tracking.
Not only the code is much smaller, but the performance shot up to the 85% percentile. Genius!
Thank you Ben.
ye
You need to use leftSerialized and rightSerialized instead of leftSubtree and rightSubtree
ok
I have not watched till solution yet, I feel so stupid, this is my thoughts.
We can have not symetric tree, that's our problem, because we need to get string, which can be deserialized back, so we need to have a pattern, but what we can do with nodes that have not pair node in other side of the tree? There are 2 ways, detect them in our serialization function and put whitespase or something else at string, to make clear that there are no node.
Or we can copy our tree and make it simetrical and put something which will indicate for deserializer that some X node does not exist .This is bad idea.
ur good
Awesome video as always. Just curious, how do you synchronize what your about to say and the code/text overlay (which is added post recording) ?
I just shoot with a loose vision for how I will edit it later. At every point in recording I have a visualization of where I am in the lesson running my head as well as where I want to go, what things I can pop in, etc.
It is funny, there are so many tricky nuances because once it is shot...it is shot...you can't put yourself in a position where you need to "undo" what you said or wrote.
The video is made with the end in mind, so the planned editing drives how the lesson takes shape.
When queue becomes empty and poll method returns null. calling equals() method on null will throw NullPointerException. So how this case is being handled in the code I couldn't understand. Could anyone explain this please ?
I'd answer but I'm rapid replying to comments, I saw this and don't remember the code
so hard to understand what is actually happening in every step when you're not painting it on the board (like you did in the reversed linked list problem).. trees+recursion are tough to grasp
True mate!
The way you try to emulate our thought process in our brain is amazing.
I like ur ways explanation. Starting from scratch. Keep it up
ok
Put pewdiepie vs t-series in the title of your video.
or maybe make a mini javascript game about pewdiepie vs t-series to get few subs faster. Essentially use whats trendy like what Jarvis did. One problem though is that you might lose track of what you are doing just like jarvis.
on the other hand you can do more collabs like you did with gaurav.
hahaha, yeah I know, I watched the Jarvis ascent to fame and took note of all the little things he did (once that 1 vid blew up he doubled down on that content type). But that's the problem...I want to stay informational too...like this whole project started because of a deeper purpose and I can't sell that out for growth (even if these videos are less scalable attention-wise).
And yeah, collabs are a thing too. Yeah.
I just subbed. I've never before subbed when asked, it always sounds needy and annoying but somehow your totally genuine plea got me like "yeah, this dude needs subs"
Great video mate. Keep it up
hahahahahaha thanks
3:19 pre-order traversal - DFS (null return/node/defer)
Lintcode :www.lintcode.com/problem/serialize-and-deserialize-binary-tree/description
BFS solution: www.jiuzhang.com/solution/binary-tree-serialization/#tag-highlight-lang-python
what I do
Leetcode difficulty ratings make 0 sense. I've done problems where they're hard and I thought they were easy and vice-versa.
yeah, difficulty is relative to absolute complication & the person themselves
Can anybody explain me why the deserialisation code won't always generate a left skewed tree?
Someone help
OMG !
Brilliant Explanation.
And I keep saying this in every video of yours, can't help myself !
ha, im decent
Isn't the queue being passed to every recursive call kind of global state?
I dont remember the code
IMO, level order (bfs) is more intuitive as we can work with queue in both the methods
yeah
This was immensely helpful for clarifying my confusion on the details when I was trying to implement this myself. I really like how you walk through your thought process step by step. Thank you!
sure
Ben, your explanations are amazing! Every time I get stuck doing a problem, I just pray that you have a video on how to solve it because none of the other RUclips videos stick as well as yours do. Thank you so much for this!
Seriously. Copy pasting another comment 🤦🏻♂️
There isn't really an explanation here as to why 'preorder' is chosen to serialize compared to the other traversals. How do we know preorder will work when deserializing compared to inorder, for example?
it was arbitrary, anything can be used as long as it is reversible
@@BackToBackSWE That's exactly my question, how do you know it's reversible and that it works?
I think after the first deserializeHelper recursive call, the nodesLeft will be reduced to an empty queue. Where am I wrong?
I dont remember
@@BackToBackSWE I know where I'm wrong, whenever a null (or X) is polled from the queue, deserializeHelper will return instead of further reducing the queue. Thanks for your awesome video!
I remember I have seen a problem on leetcode that asked to deserialize a tree based on pre-order and in-order traversal. Looks like in-order does not really give us anything, and simply pre-order or post-order is enough to deserialize. Why would there be a variation of the problem that gives us an in-order serialization as well?
not sure
nicely explained i have become fan of u.
thanks
Such a high quality and complete video. The text animations really helped solidify my understanding of the solution.
nice
Thanks for explaining the thought process behind every step in the solution. A lot of youtubers and websites just give you the solution but in a real interview you have to express your thought process and it is more important than the actual solution. Please keep covering the thought process in your future videos too. You're doing a great job!
sure
Problem + Fun + Solution = BackToBack SWE 👌
ye
Thanks, make a donation portal, maybe you can get financial help while doing this stuff.
I have a Patreon but stopped promoting it. I want to focus on building products for this project for the 2nd half of 2019.
I can only say thank you!!
Ben, you're incredible at explaining problems. I hope I would see this video before march 2019 when I failed an interview that was about this, but this year is going to be different!
By the way, you did not say the Time Complexity and Space Complexity of this algorithm. If I am not wrong, it is O(N) time complexity (N = numbers of nodes of the tree) and O(H) complexity (H = height of the tree, number of levels) because of the recursion stack.
Best wishes!
thanks
why is it O(h)? I understand that recursion will take up to O(h) memory, but you have to recreate the entire tree (algorithms calls new TreeNode for every node), so it's complexity should be O(n), where n is the number of nodes. Please correct me if I'm wrong !
hmm.. or you're just talking about the additional space complexity?
In the beginning you said you are going to do a Preorder traversal but i believe what you did was postorder traversal
We visit node left right I believe (did this a while back) which is a preorder traversal.
You serialize the left node first than right node and then merged root.val with it i am not sure how it is preorder. May be i am missing something
Glad that you achieved and surpassed your 100k goal. Thanks for your videos
Hi there. Just to say that this question was asked to me in an interview in a big N. Thanks for your work, you are absolutely the best!
Please keep doing this videos! You are amazing.
sure
@@darod6098 ok
What's the difference between Serialize and Deserialize BST and Serialize and Deserialize BST in terms of the strategy?
what do you mean?
@@BackToBackSWE Sorry, typo, I mean Serialize and Deserialize BST and Serialize and Deserialize Binary Tree
@@wentingsong9435 Should there be a difference, what optimizations could be done for a BST? I'm thinking too, not sure what an ordering property brings to the table to beat O(n) time...since we must touch all nodes to uncover their value.
Amazing stuff dude, already recommending to friends :)
thanks
Oh man! You are simply great
Your explanation is so clean and easy to understand! New subscriber here ;)
yo, thanks
Here is the complete code.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return serializeHelper(root);
}
public String serializeHelper(TreeNode root) {
if(root == null) {
return "X";
}
String left = serializeHelper(root.left);
String right = serializeHelper(root.right);
return root.val + "," + left + "," + right;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue queue = new LinkedList();
queue.addAll(Arrays.asList(data.split(",")));
return deserializeHelper(queue);
}
public TreeNode deserializeHelper(Queue nodesLeft) {
String value = nodesLeft.poll();
if(value.equals("X")) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(value));
node.left = deserializeHelper(nodesLeft);
node.right = deserializeHelper(nodesLeft);
return node;
}
}
And here you are in < 3 years you have > 100K subscribers. You guys are awesome!
Edit: I am considering paid subscription is everything is explained in java?
Wait, isn't the queue of node values global state?
this is a very clever code where we are doing a bottom-up approach of pre-order traversal....from just looking, it will be like we are trying to do a post-order, but the way we combine string in serialize(..) is actually pre-order bottom up style.
Whenever I search for a problem, at the end I add "Back To Back SWE" if I don't get the video I start hating the problem. I wish if there were all the solutions that we need, recorded by you.
I just found this video and this channel, can't believe I did not come across this ever. I was stuck bad time and its a treasure, and the way you explained everything totally worth it! Thank you!
welcome
well i guess the hardest part to imagine the recursion it's when you think you should compare the left or right node with the root on each time but with the representation of 1,2,x,x,3,4,x,x,5,x,x this representation where we find the x will stop the propagation to left node leading to right node thanks for the explanation
This was fucking awesome, man. Interviewer will go crazy if explained like this in actuall interview. Respect Man!
Hi, I want to serialize and deserialize a graph. The function serialize should give me a vector of integers and the deserialize should accept this. The graph can have cycle. Does anyone have any idea?
Why can't we use the string array instead of the queue?
We can do it however we can make work
You are awesome, and I see that you hit your 100k Mark! Cheers brother. Here is to a million!
indeed we did and yes
Wow, after watching your explain then I can solve this question by myself.
Thanks a lot !
You probably should have said "Another one" instead of "Next one" ))
- Please describe Queue structure.
- First comes and after that another one and Another One, and Another One, and Another One.....
ok
Why are we using a delimiter? Isn't a string essentially a character array and we can use an index to extract each character in the string? Somebody please explain? Why can't I store the string in a queue instead? 😭
So this then should also work if you'd do a post-order or in-order traversal right? It seems to be that the key is that both serialization / deserialization need to have the same traversal.
if it is an empty root, are we still returning NULL_SYMBOL + DELIMITER?
Great use of data structures. Generally, the first instinct is to use a global state and when that is thwarted, I usually get flustered. This approach showed me a different way to tackle solutions. Also optimizations cz the global state would probably just add to the memory usage.
nice insights
Isn't this Post-Order traversal? You are recursive going all the way to left, then right and only then extracting the value of the node.
Did I say that? I was speaking from the code: github.com/bephrem1/backtobackswe/blob/master/Trees%2C%20Binary%20Trees%2C%20%26%20Binary%20Search%20Trees/SerializeDeserializeBinaryTree/SerializeDeserializeBinaryTree.java#L37 - maybe I misspoke
Its interesting how you don't even have to check that the queue is not empty, because your string will always end with an X
Wow! That was so very well done. A lot of tutorials just say that "Use a Queue" and mostly don't explain "WHY". You sir, did that part and you did it beautifully! Good Luck and I hope you hit 100K subs soon! ♥️
Haha thanks and yeah, it'll happen with time. I'm impatient.
@@BackToBackSWE haha, cover yourself with more problems and you won't have the time to think about the sub count ;)
@@9429963654 😏😏
when is a video coming through?
thank you so much for this tutorial. super clear and was able to solve that problem on leetcode right away.
I really like your approach of thinking to the problem and decomposing it into steps. Thank you very much. Please keep posting such videos especially on dynamic programming which is kind off little hard. Thanks again for helping the society!!!!!! :)
ok
There is one similar questions about binary search tree. We dont need to include null . You guys can check.it out.
Keep up the great work my man, doing all of us of a great favor! Spread the knowledge!
ye
Create heap kind of array join with comma then create a string separated with comma easiest way to serialize and deserialize
If you just represent the tree as an actual array you could just serialize the array, job done lol
sure - level-order works
Great video and crisp explanation. Understood the serialization, but still trying to comprehend the deserialization. New subscribre here!! Keep up the good work.
yoyo
Thankx buddy, your way of explanation is awesome. Thanks once again.
thanks and ok
Clear explanation, I like it so much, can I transfer it to other websites, so that more people can see.
great to hear
9:59 how is it considered as passing around state?
rapid replying to comments, can't look into this I am sorry
Congrats ! You acheived your goal
yes I did
In the serialize function, I think you are not actually assigning the numbers? or am I missing some point? I mean you say that the output is "1,2,X,X ... " but you don't really add in the numbers. Thanks for the vid btw, very well explained
what do you mean?
@@BackToBackSWE ohhh sorry :') I missed the root.val part
He doesn't even need to write anything, visualization does the work. Legend.
Just watching this video first time, hearing you say you want 100k subscribers in a year or two, seeing the video came out 2 years ago, and seeing 188k subscribers made me happy for you
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Very clear and nice explanations dude ! You rock ! You just got a subscriber
thank
Are you doing post order traversal while creating the string during serailization?
Thanks a ton !. One day you're gonna make a ton of money making these videos that you'd want to quit your FANG job.
Hahahaha, I didn't start for that & it's be a struggle finding a way to make this work...eh...it's a pipe dream
This is pure gold
Thanks
is there any way to communicate with you ?
yes backtobackswe.com/contact
Congrats on 100K! Pretty big achievement on your end - big resume flex too haha
thanks - I have no interest in creating a good looking resume. I only want to make legitimate things in the world that are very large and help people.
thanks for answering dont forget to add about 2-3 trees...........keep it up men its good is better from other explanations
thx
Thank you very much! Subscribed! Also the face on 8:08 is epic
What did I do - I'd prefer to not know
Thank you for the video. Explanation is really good