Construct BinaryTree From PreOrder and InOrder Traversal | Leetcode 105 Solution

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@betabias]

the amount of effort you put in each video motivates me to learn more, thanks

[@trevorPhillips284]

please make yourself translucent whenever you write something behind yourself

[@shivammishrasvnit5456]

Thanks a lot sir as only you i feel in yt till now who hadnt directly write code without explaining inside functioning of recursion Thanks a lot sir.

[@pr1493]

😂

[@namanshah2688]

Thanks sir it was very clear and intuitive.

[@Pepcoding]

Keep watching. For better experience visit on nados.pepcoding.com

[@tathagatnegi5923]

Haircut 👍 looking good sir

[@samadsiddiqui5925]

Thanks for explaining it in the depth.

[@vrajeshbadgujar]

Thanks

[@_justacoder_]

Very helpful content thank you pepcoding !!

[@Pepcoding]

Glad it helped!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com

[@NeerajSharma-mz4es]

sir bahut saari videos playlist me nhi h trees ki merge kr dijiye please

[@AnuSharma02]

God explanation! 🙏

[@sudhanshuuniyal5737]

great channel.

[@aashishgoyal1436]

nice explanation sir

[@adilkhatri7475]

instead on finding element index every time create hashmap with value->index mapping this will reduce the time complexity to O(n^2) to O(n)

[@suvamgupta2914]

Will it work in case of duplicate elements??

[@adilkhatri7475]

@@suvamgupta2914 No.

[@suvamgupta2914]

👍🏽

[@neelam5170]

finding using linear search will also take O(n) without extra space....hashmap would take up O(n) space as well

[@suvamgupta2914]

@@neelam5170 O(n^2) hoga worst case without hashmap kyuki har node k liye iterate ker k index nikalna hoga

[@SumitSingh-ui4do]

Thanku again sir❤️❤️

[@Pepcoding]

For better experience, visit nados.io, where you will get well curated content and career opportunities.

[@studyafa7159]

10:00

[@ketansharma6955]

nice

[@aadil4236]

kya ye tree binary search tree hoga ya, binary search tree or binary tree hosakta he?

[@divyanshukoshta2443]

sorry but video is not goodf

[@vishalbansal6925]

is time complexity here is O(n^2) here ? And is there any other way to optimize it?

[@faizan346]

yeah i think if we store inorder index in hashmap , its value as a key. then it will become O(n)
unordered_map umap;
TreeNode *buildTree_(vector &preorder, vector &inorder,
int ps, int pe, int is, int ie) {
if(is > ie || ps > pe) return NULL;
int idx = umap[preorder[ps]];
int clst = idx - is; //countLeftSubTree
TreeNode* root = new TreeNode(preorder[ps]);
root->left = buildTree_(preorder, inorder, ps+1, ps+clst, is, idx-1);
root->right = buildTree_(preorder, inorder, ps+clst+1, pe, idx+1, ie);
return root;
}
TreeNode *buildTree(vector &preorder, vector &inorder) {
if(preorder.size() == 0) return NULL;
int ps = 0, pe = preorder.size()-1;
int is = 0, ie = inorder.size()-1;
for(int i = 0; i < inorder.size(); i++) umap[inorder[i]] = i;
TreeNode* root = buildTree_(preorder, inorder, ps, pe, is, ie);
return root;
}

[@shivanshpandey4495]

@@faizan346 Thanks Brother

[@BrajeshKumar-ry8qt]

@@faizan346 What if we have duplicate elements ?

[@srijitmondal4190]

@@BrajeshKumar-ry8qt in the constraints of the question it is mentioned that the elements are unique

[@devanshubilthare5277]

Sir, I think this code is better, no need of passing preorder starting and ending index.👇👇👇
static HashMap hm = new HashMap();
public static TreeNode buildTree(int[] preorder, int[] inorder) {
int idx = 0;
for(int val: inorder){
hm.put(val, idx++);
}
return buildTree(preorder, inorder, 0, inorder.length - 1);
}
private static int preIndex = 0;

public static TreeNode buildTree(int[] preorder, int[] inorder, int start, int end){
if(start > end)
return null;
TreeNode node = new TreeNode(preorder[preIndex++]);
if(start == end)
return node;
int idx = hm.get(node.val);
node.right = buildTree(preorder, inorder, idx + 1, end);
node.left = buildTree(preorder, inorder, start, idx - 1);
return node;
}

[@MohitGupta-sz2cv]

Dry run on below Test Case :
6
In-Order : 3 1 4 0 3 2
Pre-Order : 0 1 3 4 2 3

[@mridulgupta4185]

On leetcode it shows runtime error but i dont know why

[@devanshubilthare5277]

@@mridulgupta4185 ohh, strange

[@shadman346]

this code is wrong you are only passing range for inorder without specifying postorder range

[@nandinibagga4857]

variable names confuse kr gye🤔

[@shivammishrasvnit5456]

watch again you will get

[@vaibhavchhabra800]

Too tough to understand

[@sarveshjhunjhunwala5606]

very bad handwriting! 'n' ,'h' and 't','i' look same !

[@shivammishrasvnit5456]

look at his beautiful explanation how he explained each line of code no one in yt of this question has courage to explain recursion how is it work line by line.

[@SharjeelTahir-lq3tx]

​@@shivammishrasvnit5456 his explanation actually kind of sucks. Some parts are good but some parts suck. This guy is amature. he thinks dramatization of the procedure will make it more helpful to understand. But that is where he needs to provide insight instead of dramatization ex. "give command to these number to form left subtree"