Create Binary Tree from pre-order and in-order traversal (LeetCode 105) | Easiest explanation

Actual Problem: leetcode.com/problems/constru...
Chapters:
00:00 - Intro
00:58 - Problem Statement and Description
03:09 - Where to start?
08:45 - Dry-run of Code
12:47 - Final Thoughts
📚 Links to topics I talk about in the video:
Binary Trees: • Binary Trees Introduct...
Pre-order Traversal: • Pre-order traversal of...
In-order Traversal: • In-order traversal of ...
Recursion: • Recursion paradigms wi...
Divide and Conquer: • Divide and Conquer alg...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

[@kunalkheeva]

i could not get the rootIndex + mid-left + 1 part, and unfortunately you did not explain it in the video as well, could you please explain how the root of right is starting from here?

[@junaidahmad9105]

The root for the right side can be found by adding the length of the left subtree (mid-left+1) that's why you update it with that

[@bahutbadiyakp]

isko bhi nhi pta iss formula ke baare mein... muje toh bahut confusion ho rahi hai.

[@vivekk251]

@@junaidahmad9105 Thank you very much for this comment.

[@nishantparaskar2048]

@@bahutbadiyakp the formula `rootIndex + (mid - left) + 1` ensures that we correctly identify the starting point of the right subtree in the preorder array, by skipping over the root and the entire left subtree. - `rootIndex`: Current root index in preorder. - `(mid - left)`: Number of elements in the left subtree. - `+ 1`: Skip the root element itself.

[@dipenlama4431]

Really like the visualization of the problem and how tree is constructed. Really helped to understand the problem. Thanks

[@archu0078]

Amazing and easy to grasp the concept with your explanation. I got really interested in studying Algo and Data structure with your videos. Really appreciate your way of teaching. Keep up your work

[@user-hp1ow7cu7o]

Great explanation. Thank you very much

[@kidscodera3043]

lots of love brother. I have been watching your videos for leetcode sokutions. thanks a lot for making such videos !!

[@nikoo28]

So nice of you

[@preetomadityapranoy429]

Keep up the excellent work. Your explanation technique is brilliant.🤩🤩

[@MuktoAcademy]

Great explanation

[@nikoo28]

Glad you think so!

[@eeengineer3952]

Being from a non-cs background, I'm struggling with dsa, glad to have discovered your channel. You've made the understanding so simple. Even though I've gone through the core java, I'm unable to come up with an approach to solve such questions, can you please suggest me regarding how to approach such problems.

[@nikoo28]

while there is no definite approach, the best you can do is practice. Start with some of the concepts first. Algorithmic Paradigms: kzbin.info/aero/PLFdAYMIVJQHOvoD4gQz7CwEhK3pAXWLdX Once you start to understand it, try writing some basic codes. Get started with easy problems: kzbin.info/aero/PLFdAYMIVJQHMap2jOyU6-kHjQEL-vxlV2 This way you will start to build confidence.

[@pcccmn]

I think it's insane how you did not even use array slicing like NeetCode does. well done & thanks

[@sudesh6807]

Have seen neetcode video on this problem. array slicing is a expensive operation. There is a good chance the interviewer Might ask to optimise it. Also I found neetcode explanation better. If nikhil did a dry run to explain the start index of right subtree this would have been easier

[@nikoo28]

you use the map to get the start index. It will return you in O(1) time...fastest.

[@subee128]

Thanks

[@iiju8212]

Just discovered your channel and subscribed. Great way of teaching! Please try to include Python code as well if it's not much since there aren't many python dsa/leetcode content creators.

[@nikoo28]

thank you for subscribing.. :)

[@nikoo28]

also, I usually focus on understanding the problem and how to solve, rather than the programming language :)

[@1murkeybadmayn]

i don't understand, if rootIndex is what is used to create the root, then when you do rootIndex + 1 how is it creating the other 'roots' (nodes)? It's easy with the first root because you're just inserting it from the start but i don't get the recursive part. It would have been helpful if you showed at least two iterations instead of just the root ,3, when explaining the code.

[@nikoo28]

everytime the method splitTree is called, it is creating a new root. Which gets assigned to either the left of previous node, or the right of previous node.

[@susdoge3767]

pls explain why did we write root index as rootindex+mid-left+1 in root->right call

[@nikoo28]

The idea behind this calculation is that in a pre-order traversal, the root of a subtree comes before its left and right children. So, when you move from the root of the current subtree to its right subtree, you need to skip over the nodes of the left subtree in the pre-order traversal. mid - left + 1: This part calculates the number of nodes in the left subtree. mid is the index of the current root node in the in-order traversal, and left is the index of the left boundary of the current subarray. Subtracting left from mid gives you the count of nodes in the left subtree. rootIndex + mid - left + 1: This calculation adds the number of nodes in the left subtree to the index of the current root node. This effectively brings you to the starting index of the right subtree's pre-order traversal. So, this calculation ensures that you start building the right subtree in the pre-order traversal from the correct index, accounting for the nodes already covered by the left subtree. Remember that in a pre-order traversal, the sequence goes: root, left subtree, right subtree.

[@susdoge3767]

@@nikoo28 thanks!!

[@SuriyaT3001]

Hi bro I have a suggestion can you post one vedio about how recursive backtracking works on step by step using code . Becoz I have understood while saw tree but in code I don’t know how it’s first recursive call end and how backtrack took a place and how element store in a particular list pls pls pls I am very exhausted .. I reallly searching for vedios like kind of this step by step but I can’t found anything they are simple dry run code and finishes their lecture . I want you to do this vedio pls

[@nikoo28]

Have you watched my videos on recursion? They cover all the basics.. how it happens step by step

[@shreddedvarun]

I found the recursive backtracking explanation given by Nikhil to the best in the market. I finally understood it using his technique&explanation

[@Moch117]

Can be solved with 4 pointers instead of using Map

[@nikoo28]

How?

[@VinayKumar-xs6el]

rushed

[@nikoo28]

what part did you face a problem with?

[@zhunzargulhane6741]

3rd class