LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal (Algorithm Explained)

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@ArjunKalidas]

Most of this explanation just bounced over my head! Hey Nick, can you please explain the algorithm a bit more clearly, before getting into the code. Because end of the day, logic and derivation of the solution is what matters right, and coding will be easy after that! Thanks for the video though.

[@SaurabhYadav-wj7zm]

I think he just see the code and makes the video, without even getting into the algorithm part.

[@malikwaseem1983]

Algo in the above link follows natural recursive order and thus is easy to understand and makes more sense

[@raj-nq8ke]

You can first go through theory videos and then come here to watch code explanation.

[@Aditya-rm3bl]

Not sure how he has so much followers. The solutions are either taken from solution or reporduced from memory without any explanations.

[@MrSaurus]

He's good at explaining the problems that don't involve trees, but yeah I don't like watching his tree tutorials

[@trung.n]

You can convert the in order array to a hash map storing {inorder val : index} to avoid looping through the in order array each time

[@zmanneverdie]

I find that the main time cost in this solution is from the for loop search part, you can reduce the time cost by using a hashmap for inorder element search.

[@AkshayKumar-xh2ob]

Your solutions always explain the intuition behind the solution.

[@vinothborn2win]

Thanks Nick. You are awesome! Constructing Binary Tree from PostOrder and Inorder is very similar to this problem. In PostOrder, the sequence is "left, right, center", which means we need to loop PostOrder array from the end. Recursive inputs to root.left and root.right will also differ accordingly (but very similar to this video).

[@rajman617]

Yes I can understand for root.left It will be “postEnd-1” but can you say like Wat it would be for root.right ....

[@saiyamkumarsingh619]

So finally you did this problem. I watched yesterday's live stream when you were solving this.

[@kittwwang]

Your solution is always very concise. I was coding it and got all the index mangled up. Thanks for the video!

[@brovet78]

Can you please also tell us the time and space complexity when making these video? Just subscribed. Yours is easier to understand than solution in discussion lol

[@trinhta9410]

I think the time complexity is O(N) and space complexity is O(N) if you count stack frame of the recursion.

[@arsenohanyan306]

@@trinhta9410 They are both O(n^2)

[@beyondlimits8159]

@@arsenohanyan306 how?

[@stith_pragya]

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

[@Hgh38]

Anyone think question is hard? I even saw this video and I still don’t get it.

[@FitnessChaos]

Good explanation of preorder, inorder and postorder

[@nikakondra5321]

Thank you Nick!

[@User_Unknown_Anonymous]

Just subscribed cause you said you can grow as you get more subscribers LOL We will help your channel grow, you help us learn data structures and algorithms. I appreciate you teaching us these concepts.

[@lowkey_anp]

so u knoe how to reverse a linked list, but do u knoe how to design a large scale software system

[@khandelwalsahaj36]

yes

[@suyashsorte]

Great video!!! I took a while to understand the concept. Can you tell what is the time and space complexity for this approach?

[@rasikachavan7290]

Thanks for simplifying the problem!! Can you tell time complexity and space complexity of this?

[@LtMewS]

time complexity looks like n^2 as looping to find inIndex and doing recursion takes o(n) and inside it we r looping with o(n) so its o(n^2)

[@user-mi8ew2to8e]

I didn't know Nelson Bighetti aka 'Big Head' has a youtube channel

[@killingjoyandmemeing]

lol

[@user-vu8jp3si2r]

Why code in this video get stack over flow?

[@arianphilips5777]

It took me 1 hour to do this problem, and you just did it in 11 minutes DAM

[@sumandutta83]

there was a leetcode pre-existing solution :-)

[@yashsvidixit7169]

And I can't understand it for a month now, FML

[@sohamharnale2878]

Do you solve problems live on Twitch? Would love to be a part of it!

[@_sf_editz1870]

Coolll easiest explanation on internet

[@emansrnme1371]

If I am a novice to trees, what can you recommend? I couldn't understand the video.

[@chiranjeevipippalla4483]

I would recommend you to watch the videos of mycodeschool for basics of trees. They are very clearly explained. Once you get an idea of those concepts, watch these videos. You will find this easy.

[@emansrnme1371]

I understand what are trees now, can write a search and insert, but still don't understand this video

[@ramchandrayadav8378]

@@emansrnme1371 You should try by yourself. I solved this problem by myself without using hashing. I am also a novice . I came here to learn a different approach for solving this problem, using hashing which i couldn't understand .

[@rajman617]

@@emansrnme1371 keep learning and solving these kind of problems . Trust me you will start learning as you keep practising. In the start it looks “BLANK” but as the days go ... we start understanding each and every bit .

[@trinhta9410]

it is hard to understand the formula for the prestart of the right nodes. My solution was passing prestart as reference and increment its by 1 for every-time a node is created. Thank you for your video.

[@darod6098]

Thanks for the video, it helped me. Do you know what would be the approach if the array would have repeated elements? (or the work around)

[@lazycoder1910]

Thanks for all ur work!

[@evgeni-nabokov]

Is there a way to improve look up for the inIndex?

[@anirudhatalmale5575]

Awesome explanation. Thanks

[@user-bi4gg9he7v]

But in other sites like gfg they are passing preStart as prestart+1 in both root->left and root->right and still giving correct output. Can you explain why?

[@SnowFlameSupremacy]

I'm late but thats because they are using global variable... the method is good but the problem is leetcode doesn't execute it right for some reason ....meaning it works when ur executing urself for test cases but when submitting it gives wrong answer

[@SnowFlameSupremacy]

I'm late but thats because they are using global variable... the method is good but the problem is leetcode doesn't execute it right for some reason ....meaning it works when ur executing urself for test cases but when submitting it gives wrong answer

[@calfland79]

In line 29, where does inIndex - inStart + 1 come from? In other words, how do you map inorder index to preorder index?

[@RajatGautamism]

he is just skipping number of element which are supposed to be on the left subtree, from looking at number of elements in inorder array.If you didn't get this then go through recursion concepts again.

[@joanperezlozano7405]

This might be a late response, but perhaps useful for newcomers... in addition to what Rajat said, this is sort of like a small formula to count in a set of consecutive numbers (in this case our set is the indexes) so we count from one position to another (greater number - smaller number) and then you + 1 to make an inclusive count or -1 to make an exclusive count. E.g try with counting numbers from 3 to 6 inclusive, for the set: [0, 1, 2, 3, 4, 5, 6, 7] -> 6 - 3 + 1 = 4. Same concept is applied to know how many indexes we want to skip in the preorder array to build the right subtree.

[@rodanm]

Nick, can you share your 2ms submission? Thanks

[@MrThepratik]

nailed it . thanks for the clear explaination

[@adamberry7536]

You can save the value and index lookup for the inorder in a hashmap to avoid the for loop in your recursive stack.

[@cathywei8842]

Thank you ! really helpful!

[@vasanthakumarn7196]

Hii bro can u solve HOUSE ROBBERY 3 problem ? Under tree category

[@ShubhamVerma-cn7bc]

Nice Video, gr8 explaination

[@sophiezhang6516]

good explaination!

[@mandar.vaidya]

thanks nick

[@zahash1045]

could you please zoom out a little further, please? Who wants to see what's being typed on the screen anyways

[@akrmh9934]

good explanation but the screen is far....i can't see obviously

[@buttekaustubhpradeep5566]

Yo nick

[@supermadhujya1]

great video man

[@demidrek-heyward]

not sure why people dislike these videos?

[@demidrek-heyward]

like be more appreciative wtf

[@karankanojiya7672]

Beauty Nick !!

[@shubhamtiwari6660]

That wasn't a bad Al Pacino impression. And Thanks dude, your videos really inspires me to code.

[@yv6358]

you get my stuff. Watch and subscribe so that I can grow my thing. What is he referring to

[@son0funiverse]

Yeah, this was a doozy

[@Vishal-joshi1998]

complex

[@jamesgeng7815]

Man! It does not look like you in this video, you must have drive some vodka...

[@ahmedfattah5879]

3

[@aaronlong1298]

His attitude is kind of the worse, It's extremely hard to get through this because of it. I can feel condescension permeating this video.

[@vk1618]

Review

[@ajaytyagi3018]

f

[@HridayGandhi-ix3gl]

ur explanations are not clear and understandable you should be first clear urself and then teach others

[@abhinavrana5356]

Pretty stupid explanation tbh

[@pankajrathi]

Kevin >> Nick