Serialize & Deserialize A Binary Tree - Crafting Recursive Solutions To Interview Problems

Подписаться 240 тыс.

Просмотров 102 тыс.

50% 1

Code & Problem Statement @ backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 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.geeksforgeeks.org/compile...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
Elements of Programming Interviews problem 10.13

Наука

Опубликовано:

30 апр 2019

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 385

@BackToBackSWE 5 лет назад

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.

@atanxellos2160 4 года назад

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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-suj1ro8TIVY.html Both pointers point to the left node, instead of left and right.

@BackToBackSWE 4 года назад

@ousmand742 4 года назад

When Im stuck on a problem I say a silent prayer that BackToBack SWE has covered it on video

@BackToBackSWE 4 года назад

lmao

@sandhyagupta7359 4 года назад

that is so true

@akshay8675 4 года назад

💯

@raevenbauto1578 3 года назад

Lmao this is so accurate!

@willturner3440 3 года назад

😂LMAO

@ahmadkhaled4233 4 года назад

thx Bro

@BackToBackSWE 4 года назад

nice!!

@lilley2595 4 года назад

ممكن اعرف ايه المصادر اللي درستها للمقابله

@BackToBackSWE 4 года назад

@@lilley2595 Indeed.

@ahmadkhaled4233 4 года назад

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

@AidenLeeyong 5 лет назад

I really liked that you also explained mental barriers like this. I appreciate it.

@BackToBackSWE 5 лет назад

haha nice

@CollectConnectDots 4 года назад

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.

@BackToBackSWE 4 года назад

ye- we shall see what i do

@BasharAlkhalili 4 года назад

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.

@BackToBackSWE 4 года назад

@PankajC 5 лет назад

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!

@BackToBackSWE 5 лет назад

sure

@andrewcrenwelge5592 5 лет назад

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!

@BackToBackSWE 5 лет назад

sure

@malihaislam711 4 года назад

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 RU-vid videos stick as well as yours do. Thank you so much for this!

@BackToBackSWE 4 года назад

hahaha nice, well glad to head that

@sarthakgupta072 4 года назад

@sihatafnan5450 3 года назад

The way you try to emulate our thought process in our brain is amazing.

@Chaitra.Rai. 4 года назад

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!

@BackToBackSWE 4 года назад

welcome

@hassankazmi5443 4 года назад

Keep up the great work my man, doing all of us of a great favor! Spread the knowledge!

@BackToBackSWE 4 года назад

@yiyingzhang9585 4 года назад

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.

@BackToBackSWE 4 года назад

@SergeNevsky 3 года назад

It's really cool to see that you wanted to reach 100k+ subscribers in two years, and now two years later you're at 138k.

@D-Daws 4 года назад

Such a high quality and complete video. The text animations really helped solidify my understanding of the solution.

@BackToBackSWE 4 года назад

nice

@atulmalakar 4 года назад

OMG ! Brilliant Explanation. And I keep saying this in every video of yours, can't help myself !

@BackToBackSWE 4 года назад

ha, im decent

@anuragtiwari3032 2 года назад

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!!

@EsotericArnold 4 года назад

this is amazing! I kind of got it from binging on your work yesterday but this really lays the idea and the way of reasoning about the tree traversal, flat for me.

@BackToBackSWE 4 года назад

great to hear

@harshitrastogi9078 5 лет назад

This is the best explanation of this problem ever given. Great job!

@BackToBackSWE 5 лет назад

thanks

@ericj1380 4 года назад

Love the channel and truly appreciate all your efforts to help others better understand these topics.

@BackToBackSWE 4 года назад

sure

@Max-zf5ot 5 лет назад

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?

@BackToBackSWE 5 лет назад

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

@PoshanBastola 4 года назад

Wow, I was just overthinking this thing. You made it look so simple!Thanks!

@BackToBackSWE 4 года назад

Nah, it is pretty hard at first, this is a polished video and doesn't reflect seeing the question for a first time

@priyankajadhav2405 2 года назад

Love the way you explained the problem by breaking it down, please keep posting Medium and Hard questions, it would really help.

@darod6098 5 лет назад

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!

@darod6098 5 лет назад

Please keep doing this videos! You are amazing.

@BackToBackSWE 5 лет назад

sure

@BackToBackSWE 5 лет назад

@@darod6098 ok

@akhildhiman8791 4 года назад

Broo!! You are awesome I was stuck on this question for the whole day but after watching this video this hard problem felt like too easy. Thanks a ton for this video!

@BackToBackSWE 4 года назад

No ur awesome

@omkarvaidya8520 4 года назад

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.

@BackToBackSWE 4 года назад

thanks

@azharhaque4217 2 года назад

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

@BackToBackSWE 2 года назад

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

@uncaged3076 3 года назад

Glad that you achieved and surpassed your 100k goal. Thanks for your videos

@trudyandgeorge 4 года назад

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

@BackToBackSWE 4 года назад

hahahahahaha thanks

@ekejma 3 года назад

HIs talent for explaining is just what you need for a deeper understanding.

@saigundlapalli3548 5 лет назад

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

@BackToBackSWE 5 лет назад

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.

@9429963654 5 лет назад

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! ♥️

@BackToBackSWE 5 лет назад

Haha thanks and yeah, it'll happen with time. I'm impatient.

@9429963654 5 лет назад

@@BackToBackSWE haha, cover yourself with more problems and you won't have the time to think about the sub count ;)

@BackToBackSWE 5 лет назад

@@9429963654 😏😏

@suyashsavji5189 3 года назад

He doesn't even need to write anything, visualization does the work. Legend.

@monicakulkarni3319 5 лет назад

I loved the way you explained this! Thank you so much, subscribed.

@BackToBackSWE 5 лет назад

aw thanks

@MarshallThrottler 3 года назад

You are the best teacher I have seen in my entire life sir! Thank You so much for ur efforts!

@BackToBackSWE 3 года назад

sure!

@yudiks 5 лет назад

Oh great job with the explanations. I felt like i learnt something new.

@BackToBackSWE 5 лет назад

nice

@niyas09 5 лет назад

i really like your explanation on tress problems.. helped me a lot.. great job!

@BackToBackSWE 5 лет назад

nice

@bibliophileanki 4 года назад

Great video and crisp explanation. Understood the serialization, but still trying to comprehend the deserialization. New subscribre here!! Keep up the good work.

@BackToBackSWE 4 года назад

yoyo

@bryanlozano8905 3 года назад

Wow, just got this question in the wild. Thanks for helping me ACE a phone screen!

@mashak3765 3 года назад

thank you so much for this tutorial. super clear and was able to solve that problem on leetcode right away.

@mohammednadeem333 4 года назад

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!!!!!! :)

@BackToBackSWE 4 года назад

@satviksharma4897 4 года назад

Thanks for such a great explanation. Please keep up the good work. Thanks!

@BackToBackSWE 4 года назад

sure, ok, and thanks

@shivabhusal5328 4 года назад

Brilliant explanation! Made my day! Thank you so much.

@BackToBackSWE 4 года назад

sure

@sairammaddala9069 9 месяцев назад

This is by far the best explanation I have seen for this problem, Thank you

@BackToBackSWE 9 месяцев назад

Happy Halloween 🎃 Very nice of you, sairammaddala! Let us know other topics we could cover! We'd love to offer you 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50

@adebs 4 года назад

amazing explanation, thank you so much!

@BackToBackSWE 4 года назад

sure

@geekySRM 3 года назад

This was beautiful!

@MZ-uv3sr 2 года назад

ooh, so much better than the first one I saw, thank you

@df4privateyoutube722 4 года назад

Congrats on 100K! Pretty big achievement on your end - big resume flex too haha

@BackToBackSWE 4 года назад

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.

@shruthib3366 4 года назад

Really loved the way you helped us understand it!

@BackToBackSWE 4 года назад

sure

@dpfit 4 года назад

Such a beautiful explanation. Thank you so much.. Subscribed right away. :)

@BackToBackSWE 4 года назад

sure

@VigneshDhakshinamoorthy 3 года назад

You are awesome, and I see that you hit your 100k Mark! Cheers brother. Here is to a million!

@BackToBackSWE 3 года назад

indeed we did and yes

@UrGuru 4 года назад

This is pure gold

@BackToBackSWE 4 года назад

Thanks

@NubmerSeven 5 лет назад

Amazing stuff dude, already recommending to friends :)

@BackToBackSWE 5 лет назад

thanks

@danni6113 5 лет назад

Your explanation is so clean and easy to understand! New subscriber here ;)

@BackToBackSWE 5 лет назад

yo, thanks

@ankitshah692 4 года назад

Very clear and nice explanations dude ! You rock ! You just got a subscriber

@BackToBackSWE 4 года назад

thank

@b9944236 9 месяцев назад

Wow, after watching your explain then I can solve this question by myself. Thanks a lot !

@vishnukumavat7489 4 года назад

Thankx buddy, your way of explanation is awesome. Thanks once again.

@BackToBackSWE 4 года назад

thanks and ok

@yzmashuai 4 года назад

The best explanation I have ever watched.

@BackToBackSWE 4 года назад

thanks

@manojkumar16 4 года назад

Very beautifully explained. Thanks a ton!!!

@BackToBackSWE 4 года назад

sure

@kgotgit3437 3 года назад

Thank you for the video. Explanation is really good

@manishrana3596 3 года назад

Congrats ! You acheived your goal

@BackToBackSWE 3 года назад

yes I did

@nokuthulambatha9980 5 лет назад

Thanks a mil for this! Bless you.

@BackToBackSWE 5 лет назад

sure

@karthikmucheli7930 5 лет назад

Dude you are so amazing. Thank God you exist.

@BackToBackSWE 5 лет назад

hahahahahaha, I've almost died like 2 times, I feel the same ha

@ashishkumarchoubey5592 3 года назад

Oh man! You are simply great

@vipulkrishna19 4 года назад

loved it. good concept concerning about only one node

@BackToBackSWE 4 года назад

@ibrahimshaikh3642 3 года назад

I like ur ways explanation. Starting from scratch. Keep it up

@BackToBackSWE 3 года назад

@kueen3032 4 года назад

Its already 99.5k, dude u r close to 100k subs. Keep up the good work, well deserved!

@BackToBackSWE 4 года назад

Yeah, what a ride. The internet is to be thanked.

@kueen3032 4 года назад

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

@manojrajasekar6035 4 года назад

Congratulations on 50k+ Subscribers Ben ! Keep doing the great job

@BackToBackSWE 4 года назад

Hahaha, I just noticed that recently. Yeah, thank you. I've been gone not because I'm actually gone, we are just working on a new platform we are launching late January. It is a "ground-up" rewrite of our website (client), api (backend), and we are writing a service to test code too. So in 3-6 months this channel will hopefully be very active again when this massive project is launched and we are just fixing bugs and making small tweaks. My goal for 2020 will be to have 300 content pieces in the platform, support 6 languages, and get this channel going again with more interesting kinds of content.

@manojrajasekar6035 4 года назад

@@BackToBackSWE OMG ! That's a great news ! Much Excited :) I was wondering and waiting for new video uploads. Got clarified now :) Looking forward to the new platform.

@BackToBackSWE 4 года назад

@@manojrajasekar6035 thx

@divyanshchowdhary5264 5 лет назад

Was asked a similar question in my interview, but instead of converting to string, had to convert it into linked list inplace. Can you please cover that in your video. Btw great video...love them♥️

@BackToBackSWE 5 лет назад

Thanks and I'm not sure if I will cover that variant. That is kind of like problem 10.14 in Elements of Programming Interviews except the whole tree. Might not be large enough of a variation to warrant an individual video (because each video takes 4-6 hours to make I can't make that time allocation).

@willturner3440 3 года назад

Bro keep uploading, you are gem of RU-vid

@osirus211 4 года назад

Cool video, man. Thanks!

@BackToBackSWE 4 года назад

sure.

@manojamrutharaj9071 4 года назад

Awesome. Yet another great presentation.

@BackToBackSWE 4 года назад

sure

@anuragv400 3 года назад

Well explained !!

@habtamuassegahegn4283 5 лет назад

thanks for answering dont forget to add about 2-3 trees...........keep it up men its good is better from other explanations

@BackToBackSWE 5 лет назад

thx

@Yobro1 5 лет назад

Thanks! Well explained.

@BackToBackSWE 5 лет назад

thx

@goofenhour2697 Год назад

Thank you! This helped a lot

@BackToBackSWE Год назад

Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

@scottliu4987 4 года назад

I like it when the codes just pop out when you are coming out with the idea

@BackToBackSWE 4 года назад

ye, is' magic

@raghavgovil7665 5 лет назад

Hey! Thanks a ton for this video! Also, I was wondering whether we could use the level order traversal to serialize our tree?

@utsavprabhakar5072 5 лет назад

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.

@BackToBackSWE 5 лет назад

Yes you can

@tanmaychandra9434 2 года назад

This was fucking awesome, man. Interviewer will go crazy if explained like this in actuall interview. Respect Man!

@pirangitharun8736 3 года назад

I wish I become like you :) You explained it as clear as possible. Thank you so much

@abhishekprasad6691 4 года назад

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.

@BackToBackSWE 4 года назад

nice insights

@fatiharslan7849 4 года назад

Dude that was epic. Thanks a lot

@BackToBackSWE 4 года назад

thx and sure

@hamsalekhavenkatesh3440 2 года назад

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.

@UsamaBinLuha 4 года назад

awesome explanation!!!

@BackToBackSWE 4 года назад

thx

@balaveeraraghavareddy9764 3 года назад

awesome explanation helped me a lot

@disola6383 5 лет назад

This is superb, for real.

@BackToBackSWE 5 лет назад

thx

@cornorange7622 3 года назад

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!

@chaupham1186 2 года назад

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.

@chiranjeevipippalla 3 года назад

Problem + Fun + Solution = BackToBack SWE 👌

@BackToBackSWE 3 года назад

@dhruvratangupta8920 5 лет назад

you're the best, thanks a ton

@BackToBackSWE 5 лет назад

sure

@TheAnilmaddala 5 лет назад

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

@BackToBackSWE 5 лет назад

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.