L48. Construct a BST from a preorder traversal | 3 Methods

Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements

[@takeUforward]

Please like and share among friends ^ _ ^ Find all links in description!

[@PrinceKumar-el7ob]

Thanks a lot striver !! Keep uploading .

[@tanmaisaichennagiri5543]

Bro if we have to just return the root of the binary tree, then we can directly say that it’s the first element in that preorder array. 😛

[@faizannasimhyder9011]

The red neon light kind of marker is cool. The way it disappears after every 2 sec😀

[@mritunjay3723]

no he makes it disappear look closely

[@saqlainkadiri]

Which app is he using on ipad?

[@Prakhar537]

@@saqlainkadiri Goodnotes

[@yt_shubham_bgp]

@@mritunjay3723 no it disappears after you remove apple pencil from the ipad screen for more than 1 sec . It comes with good notes app

[@misterr_stupied3747]

🤣

[@jayadubey_22]

thank you so much the recursion tree really helped me to understand how return statement is working 🙏

[@TaiChiSWAG]

I coded this by my own from your detailed explanation, started clicking on your videos first whenever I search for a problem. Thanks buddy thanks a lot 😊

[@parthsalat]

Binod

[@rahulraj94391]

@@parthsalat 😂

[@ayushm106]

Approach 3 : Space Complexity Doubt Space Complexity in 3rd approach should be O(N) because of the recursive stack which takes up space of O(H) and in a skewed tree H = N. Here H = height of Tree N = Number of nodes in Tree

[@PikasoCapture]

recursive stack space is not an external space, thats why its O(1)

[@anshulgoel1940]

I think some of the videos were made earlier compared to others (like this one). At that time probably he was not considering stack space of recursion as part of space complexity. But just in case anyone is confused this will be O(H) and aligned with his thought as seen in other videos. Hope this helps.

[@stith_pragya]

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

[@ravishkumar6060]

Striver's way of explaining problems itself solves more than 50% of the problem :)

[@pradipakshar]

my mans got a lil conscious about the hair 8:18 🤣🤣🤣. Nice video as usual :)

[@codeman3828]

Loved the explanation

[@vyankateshkulkarni4374]

the key point would be for above solution, for root.left pass root.val as bound and for root.right pass bound value as it is. great explanation bro. thanks

[@MyTinTin2011]

Thanks for this. I really missed this key point.

[@rushidesai2836]

Beautiful code!

[@aaranyaksantra9933]

nice solution

[@rahuldeshpande3516]

The upper bound logic is brlliant

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@dank7044]

Did this on my own

[@nishayadav3427]

Thank you so much for providing this series .

[@navendraagrawal]

the second method is actually running faster than third one

[@Shivi32590]

thank you

[@Jai_Jai_shri_Ram108]

9:58 reason why we don't consider lower bound

[@plsgivemecat]

Did it using stack. Python code: class Solution: def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]: if not preorder: return None root = TreeNode(preorder[0]) stack = [root] for value in preorder[1:]: node = TreeNode(value) if value < stack[-1].val: stack[-1].left = node stack.append(node) else: while stack and value > stack[-1].val: last = stack.pop() last.right = node stack.append(node) return root

[@rakshitpuri4192]

I used a stack to find the next greater element (right subtree) class Solution { public: TreeNode* create(vector& preorder, vector& nge, int i, int j){ if(i > j){ return NULL; } TreeNode* root = new TreeNode(preorder[i]); int rs = nge[i]; root -> left = create(preorder, nge, i + 1, rs - 1); root -> right = create(preorder, nge, rs, j); return root; } TreeNode* bstFromPreorder(vector& preorder) { int n = preorder.size(); stack st; vector nge(n); for(int i = n - 1; i >= 0; i--){ while(!st.empty() and preorder[st.top()] < preorder[i]){ st.pop(); } if(st.empty()){ nge[i] = n; }else nge[i] = st.top(); st.push(i); } return create(preorder, nge, 0, n - 1); } };

[@girikgarg8]

Exactly, this is what I though of!

[@parthsalat]

Your expressions are so good that you can also go into acting 😆

[@tanmayjoshi6762]

Hi striver, love your videos. I have one que. How is the T.C in efficient solution is O(3N) and not O(N) as it is a basic dfs traversal? Does that mean that the dfs traversals like inorder/preorder take O(3N) time instead of O(N)?

[@dhirenparekh2646]

You are right. I also got this question.

[@AbhishekKumar-vr7sh]

Yeah dfs traversal also takes O(3n) time to be precise but asymptotically it's linear time complexity

[@krishnendughosh2368]

for N -> infinity O(3N) is simplified to O(N). So it is linear time complexity.

[@factfactorial632]

I have same doubt , But i think because all the statment inside fuction just executed ones Time complexity shoud be O(N) not not O(3N)

[@stark2461]

It should be O(N) only because you can see each recursive function is getting executed only once not thrice.

[@pratyayamrit7336]

Can anyone explain why do we need to take array of int rather than just an int value of i ? Thanks !

[@anshumaan1024]

In java code ? Because in java, integer can only be passed by value, not by reference Hope it helps 🙂

[@karanbisht6359]

python solution for the same hope this will help someone!!! class Solution: def bstFromPreorder(self, preorder): h = float(inf) self.i = 0 def solve(preorder,h): if self.i == len(preorder) or h < preorder[self.i]: return None root = TreeNode(preorder[self.i]) self.i += 1 root.left = solve(preorder,root.val) root.right = solve(preorder,h) return root return solve(preorder,h)class Solution:

[@VivekSharma-eh2tv]

int the condition of or if i write a[i]>bound first , it gives me an error what is the reason behind this .. even the error cant be understood by me

[@gigglezone3432]

Can we do another way for all nodes we find their correct postion to insert using bianry search and insert it - O(nlog(H))

[@Yash-uk8ib]

sir for 2nd method (inorder one), I think it should be guarateed that the nodes will be unique otherwise, complexity will increase.

[@takeUforward]

Bst means nodes are unique 😅

[@Yash-uk8ib]

@@takeUforward oh ok!! thanks for the clarification!!

[@harshitjaiswal9439]

understood.

[@devarajm8927]

Wat if we have 4 or a 3 after 7 in your example?

[@SHASHANKRUSTAGII]

cant believe you made it so fucking easy. man

[@raunakshalya2118]

Very good explanation of the 3rd method

[@abhinanda7049]

understood

[@lavanyaprakashjampana933]

we love your content and we love you...🖤

[@somveerkhaunkar6191]

Can we implement the 3rd method using stack? I think that will be more understandable..

[@AshishYadav-ql3up]

How ?

[@PikasoCapture]

yes

[@surajbaranwal56.]

Thanks man for wonderful explanation.

[@Doraredora]

without passing i as a reference can we do it in any other way because if we forgot to keep & symbol output will be wrong thanks in advance striver sir 🙂

[@Cool96267]

why did we use reference? why is it not working without reference?

[@Doraredora]

@@Cool96267 because while doing recursion I value has to be updated if we don't pass i by reference then output will be same values try yourself :)

[@krishnasudan3410]

Yes, you can do by passing I as a variable of class. class Solution{ int i = 0; //Code Here-> No need to pass i as an argument in functions. };

[@virajnerlekar1501]

Can someone elaborate why the java code fails when we pass a variable instead or array in this case?? plz

[@SilentBeing]

Because java does not support call by address.

[@ytcc2863]

I really loved your content!!!

[@shrutiverma2594]

Why did he make the index a list and not an integer?

[@mukib_khan_]

In the first method we're just connecting the node in the bst just like normally inserting a node in a bst...is this always gonna give correct preorder bst

[@kartikking7]

can someone tell Why is variable i passed by reference??

[@sushmitaraj6948]

Because i is traversing the index of the vector . So once an element is traversed we need to move to next element and add it into the tree

[@mukib_khan_]

@@sushmitaraj6948 but we can also use pass by value right...because we're increasing the i value before passing it

[@rishabhgupta9846]

understood ,able to solve by myself

[@alephnull333]

Here to solve gate 2008 qs :)

[@vaalarivan_p]

5:05 - 8:40 edoc: 14:04

[@rohandevaki4349]

at 3:51 why is it o(n*n) ? for every node, we are taking n time complexity? and n nodes , so O(n*n ) .

[@CHANDANKUMAR-sg8cp]

O(n*n) is for extreme case or worst case as in case of skew tree for each node u have to traverse every node

[@shivarajpatil8699]

@@CHANDANKUMAR-sg8cp wrong, even or skew tree the tc would be o(n). striver's first solution is talking about inserting nodes one by one, just like in the insert node in bst question. for every index in vector we would traverse the tree for logn time and insert the node at it's place. Still it would be nlogn and not n^2.

[@pranavdua4970]

Can bound be passed by reference?

[@suryakiran2970]

Great Series

[@utkarshsharma6650]

understooooood. thanks :)

[@akshatgoyal9113]

For Method 1 and 2 it's fine but for 3rd method how will a preorder array like -> [8,5,1,7,10,2] will run it will not give correct answer with your method i think please explain

[@chiraggupta8890]

Same. Did you figure it out?

[@shivamtiwari3672]

The preorder is wrong bcz preorder is root-left-right so left is till 7 so after that all elements should be greater than 8(root) and in this input there is 2 which is incorrect.

[@your_name96]

u need to pass the index as reference or declare it as a global variable

[@user-lt2ie8ys3n]

why is the code so short

[@devanshgoel3433]

thank you bhaiya!

[@rohitchanda8461]

What an explanation!

[@momilijaz271]

done!

[@jayyy311]

💚

[@AiminglowNAccpble]

5:33

[@AiminglowNAccpble]

6:11

[@preetisahani5054]

I did it using stack: Maximum height of stack will be height of tree class Solution { public: TreeNode* bstFromPreorder(vector& preorder) { stack s; int n = preorder.size(); if(n == 0) return NULL; int i = 0; TreeNode* root = new TreeNode(preorder[i]); s.push(root); for(int i = 1; i < n; i++) { TreeNode* node = s.top(); TreeNode* newNode = new TreeNode(preorder[i]); if(node->val > preorder[i]) { s.push(newNode); node->left = newNode; } else if(node->val < preorder[i]) { while(!s.empty() && s.top()->val < preorder[i]) { node = s.top(); s.pop(); } s.push(newNode); node->right = newNode; } } return root; } };

[@gorilla_coder-el6kf]

hey how did you think of this solution can you provide me the thought process or intuition pls

[@UECAshutoshKumar]

Thank you sir

[@kartikking7]

can anyone explain how the time complexity of 3rd solution is O(N)?....I thought it would be more than that...O(NlogN) worst case i think as the largest element will take O(logN) and for N nodes we will take O(NlogN) time in total.

[@jambajuice07]

why we passed the i by reference ??

[@abhinavgarg0077]

because the I value is changing at every iteration, that's why

[@jaiminsolanki5478]

Understood

[@shouvikdatta6831]

Bro, how many more videos will come of tree topic?

[@girikgarg8]

Done!

[@sayantaniguha8519]

Iska time complexity smjh mein ni aya Backtracking ke liye alag se O(n) kiu le rahe ho

[@CHANDANKUMAR-sg8cp]

kon sa 1st or 2nd or 3rd?

[@sayantaniguha8519]

@@CHANDANKUMAR-sg8cp 3rd

[@satvrii]

❤❤

[@chandrachurmukherjeejucse5816]

Understood.

[@parthsalat]

Video starts at 6:03

[@ishangujarathi10]

intuition op!!!

[@shariqueahmadazizy1946]

BST inorded is always slrted

[@Telugu_europe]

US

[@tech_wizard9315]

I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?

[@PrinceKumar-el7ob]

Ofcourse it is enough

[@Yash-uk8ib]

practice on ur own also buddy, not everything will be served to u!

[@parthsalat]

You need to drop out of college for getting into tech giants

[@anjalik1012]

Other approch ... not the range concept, no sorting even.. class Solution { public: TreeNode* helper(vector& preorder,int ps,int pe){ if(ps>pe) return NULL; TreeNode* root=new TreeNode(preorder[ps]); int r=preorder.size(); for(int i=ps;ipreorder[ps]){ r=i; break; } } root->left=helper(preorder,ps+1,r-1); root->right=helper(preorder,r,pe); return root; } TreeNode* bstFromPreorder(vector& preorder) { return helper(preorder,0,preorder.size()-1); } }; can some one say whats the time complexity??

[@jayakantpurushoth5650]

cheers!, I just thought the same way, guess the TC is still O(n)

[@user-qq5bb7bh5z]

i think O(N * N) as for every node we find the next greater element and in worst case we that elemwnt can be at last so thats that, you can also check in gfg were they have discussed same aproach

[@GodOfFaith]

​@@user-qq5bb7bh5zexactly this is n^2 solution

[@jayant8791]

noice

[@user-up6sl2gq8p]

,.......................

[@suvanshmahajan5902]

"us"

[@siddharthsaxena6495]

What will be the time complexity of this solution??Is this efficient?? TreeNode* solve(TreeNode* root,int val) { if(root==NULL) root=new TreeNode(val); if(root->val>val) { root->left=solve(root->left,val); } if(root->valright=solve(root->right,val); } return root; } TreeNode* bstFromPreorder(vector& pre) { TreeNode* root=NULL; for(int i=0;i

[@rakshitpandey7517]

Time Complexity- O(nlogn) - as your are traversing the each node (total N nodes) using Binary search in height level and height of tree is Logn so total is nlogn. Space Complexity- O(H) average case...worst case is O(n)

[@yuktikashyap3374]

Method 3 samjh nhi aaya - tried 3 baar 😢

[@anshumaan1024]

pen paper pe dry run krke dekho, ayega samaj me

[@yuktikashyap3374]

@@anshumaan1024 yes i tried and got it but ig i still need more practice😅

[@ChetanWani-be2ew]

We can declare ' i ' as global so need to pass and it contains current value ........right....... code is working class Solution { static int i=0; public static TreeNode helper(int[] preorder,int bound){ if(i==preorder.length || preorder[i]>bound){ return null; } TreeNode root=new TreeNode(preorder[i++]); root.left=helper(preorder,root.val); root.right=helper(preorder,bound); return root; } public TreeNode bstFromPreorder(int[] preorder) { i=0; return helper(preorder,Integer.MAX_VALUE); } }

[@Auto_Enthusiast]

bhai tu pdata bhut bduya hai lekin , ye fake angrzi accent bhut annoying lgta hai , be natural man

[@priyankadas2531]

It will not work if pre Oder is 100 200 20 80 50 60 40 10

[@priyankadas2531]

When my pointer is in right node 200 for 200 left part ub is 200 so 20 will be left child of 200 acc to your logic , but manually if we do 20 will be left part of top most root which is 100

[@AmanKumarSinhaOfficial]

Next Video on Clarification about CP vs Development

[@ashutoshtripathi8257]

No already available bhai fltu videos ki demand q krte ho...ye sab Babbar Vagairah se kro

[@shubhamprasad2342]

Hey Striver love your videos been following since a long time. kudos to your hard work man. But as i saw the video the accent with which you explain kinda seemed to me that you are being a little arrogant/over-confident on yourself. May be its just me. But wanted to give you this constructive criticism hoping for better videos in future. This is just what i felt and thought of sharing. Please Don’t get offended. Thanks ☺️

[@takeUforward]

Nah nah, its the confience that i have covered in the previous videos.. haha thanks man..

[@codding32world50]

kyooo broo agar koiii best hai tum compare krlo.. striver hi hai to kyo na ho ghamand.. and i dont think its ego... if you you want to know what is ego just watch that kunal kushwahas videos you will know the difference buddy..

[@fakeid7056]

plzzz let me know why is this code incorrect on leetcode, it's accepted on gfg. Node* post_order(int pre[], int size) { //code here int i = 0; return buildTree(pre, 0, size-1, 0); } Node* buildTree(int pre[], int preStart, int preEnd, int i){ if(preStart > preEnd) return NULL; Node* root = newNode(pre[preStart]); for(; i pre[preStart]){ break; } } root->left = buildTree(pre, preStart+1, i-1, preStart+1); root->right = buildTree(pre, i, preEnd, preStart+1); return root; }

[@chiragbansod8252]

understood

[@roopeshn3301]

Understood