Construct Binary Search Tree from Preorder | C++ Placement Course | Lecture 28.3
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:
A much simpler way to do this is :
void insert(TreeNode *&root , int val){
if(root->left==NULL && root->val > val){
TreeNode *temp = new TreeNode(val);
root->left = temp;
return;
}
if(root->right==NULL && root->val < val){
TreeNode *temp = new TreeNode(val);
root->right = temp;
return;
}
if(root->val > val){
insert(root->left,val);
}
else if(root->val < val){
insert(root->right ,val);
}
}
//This is the main function
TreeNode* bstFromPreorder(vector& preorder) {
TreeNode *root = new TreeNode(preorder[0]);
for(int i = 1 ; i
I have watched only the First 50 lectures of C++ . Now , I am Here just to hit the like and i will be back upto this video after Semester Exams(During Holidays ) . Thank You !
katai bewakoof aadmi ho yr bhai tum
@@adityabhandari6688 Bhai tu Khud ko dekh le pehle phir dusro ko bolna
@@apoorvo12 sorry bhai..lekin bhai kya zarurat hai ese aake like krne ki...jab dekhoga tab hi like kr dena
@@adityabhandari6688 Baad mein ek ke bad ek video continues chalegi sirf samajhne pe dhayan hoga like and comments pe nahi isliye pehle he like kr li Videos
@@apoorvo12 okay
thankyou.found the video at the right time
Thank you 🙏🙏
May u please dryrun the code with the help of code u wrote,it would be more efficient.
not possible now, all feedbacks are futile becuase they have already shot all the videos.
@@sleepypanda7172 yes, but it really would have been great if they included dry run in the all the videos
i also need dry run of this program
Doubt : Which method has a better time complexity
1) The method shown here
2) Creating a BST like a BT which is, from inorder and preorder. Note: If we have preorder of BST, we also have inorder since inorder is sorted preorder.
Please help out.
Thanks in advance.
I guess Both of them will have same complexity of O(n^2);
bst is not totally same as bt...so this is the method
Nahi bro usme space complexity jyd hogi agr is question ko use method se krege
Ek extra vector use krna pdega inorder ke liye 🤓
this method time complexity O(n)
and 2) has time complexity O(n^2)
We can construct the tree in the normal way also, right?
Yes, but in that case time complexity would be O(n^2). Here it is O(n).
www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
@@youtuber-sl2xe nlogn not n^2
bst is known to reduce time complexity...that's why this method
There is mistake
root->left=constructBST
We has to put root->data in place of key
no bro.. we're using elements of preorder array as key.
Why are we using pointer for preorder index and why not just simple integer variable, when we are incrementing and passing incremented value will only pass then why do we need especially pointer.
Please help!
It looks less complicated using deque
node* BSTfromPreorder (int min, int max, deque &values)
{
if (values.empty())//no values left
return NULL;
int key = values.front();
if (minright=BSTfromPreorder (key,max,values);
return newnode;
}
else
{
return NULL;
}
}
please put a notes in description
Alhamdulillah 108/226. Up up and away.
why we need to do this we can simple use our precious function BuildBST from precious lactures , it can also create same BST
what is the complexity of this solution?I think O(N) .
O(n) is the optimal one , when you pass the left and right ranges,
Notes Please
Thank you to complete aman bhaiya team 😊😄😊😊😊
Perfect ❤️
I think pre-order se complexity kam ho rahi hai kyunki ismein Hume Har ek node pe Jake nhi dekhna hai array mein hi aishe sequence hai Jo hum jis node pe hain usi ke aas pass hoga is it right otherwise husein Har ek array element ke liye Har ek node pe Jake condition check karna pad jaegq
what is the need of index pointer i mean cant we just directly take the value...
i approve this video
Wait...! When we print inorder sequence of BST ..it's alwasy in ascending order ..the. Y
10 2 1 13 11
Is printed
Pla exaplain
preorder* is printed
Didi, why u have written int * preorderidx instead of int preorderidx??
cause we have to record that change in the value of i
@@tarunbisht8016 ok
@@adityaagarwal2324 if u don't wanna use a pointer just declare a static variable to keep track of the index but I will not recommend it
@@tarunbisht8016 hmm...
@@tarunbisht8016 in which year of college u r?
why we need to pass pointers?? If I remove * and & then it is only printing left tree of BST.. why we need to use pointers.
Please anybody explain!
C++ Code -
void construct(TreeNode* &root,vector& v, int &ind, int mini, int maxi)
{
if(ind>=v.size())
return;
if(v[ind]>mini and v[ind]left,v,ind,mini,v[ind-1]); // range (mini, v[ind-1])
construct(root->right,v,ind,v[ind-1],maxi); // range (v[ind-1], maxi)
}
return;
}
TreeNode* bstFromPreorder(vector& v)
{
int ind = 0;
int val = v[0];
TreeNode* root=NULL;
construct(root,v,ind,INT_MIN,INT_MAX);
return root;
}
Can't we just use the normal building bst with an array method? That too has o(n) complexity
I tried that, and getting the same solution as shradhha di.. 🙂
*preOrderIdx = *preOrderIdx + 1;
i get a different ans if i use *preOrderIdx++;
someone please explain;
do this (*preOrderIdx)++
you +1 incase of pointers and ++ in case of varialbles
hello sir 🥰
C++ code
node* build_tree(vector arr, int &i, int bound)
{
if(i==arr.size() || arr[i]>bound) return NULL;
node* root = new node(arr[i++]);
root->left = build_tree(arr,i,root->val);
root->right = build_tree(arr,i,bound);
return root;
}
node* build_tree_from_preorder(vector &arr)
{
int i = 0;
return build_tree(arr,i,INT_MAX);
}
can we construct BST from inorder alone? Please explain.
no bro we can't create a BST from inorder alone because when we have have preorder of a bst then we also have inorder( if we arrange the elements of preorder in increasing order, we get inorder sequence) it means we have both preorder and inorder.
also we can have multiple bst with same inorder sequene
No there will be multiple BST possible not a particular one
please answer my question bro
Waiting
Can someone please explain why can’t we just loop through the array and simply insert The smaller elements on left and larger elements on the right
i think the time complexity will be high if we use your approach
thats cause it wont create the tree related to the preorder
i was thinking the same we could've used the insert function that was created in video 108 of the playlist
In that case time complexity would be O(n^2). Here it is O(n).
www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
@@youtuber-sl2xe i don't understand why its o(n^2) ... it should be o(nlogn) because searching its correct position will take logn time and iteration will take n time
@doubt
Can't we generate a bst like above with the post order traversal alone??
step 1:starting from index=size-1 till index>=0;
step 2:root->right;
step 3:root->left;
someone please answer??
NO, Think for a big size tree you will get the ans
@@StoryGicRohit okay brother
Yes, we can make
Yes we can make
iss mein preorderIdx ko pass by pointer ki jagah pass by reference nhi kar sakte kya??...pass by pointer mein new memory bhi create hogi and changes reflect ho jayenge but pass by reference mein new memory nhi create hogi and changes bhi reflect ho jayenge
bhiya jaldi say upload karo naa sarray video love you bhiya i will pay you money when earn
Ye code nhi chl rha😰😰
Is input ke liye
1345,3454,1,4,2,9
,if I am wrong someone please help me
Notes upload kardo bhaiya plz...
Bhiaya ab intna aage aa gaya hu course me toh aisa lag raha he piche ka bhul raha hu thoda
Aise me kya karu isparr video bano na plss
Java ka course kab aayega
why are we making bst from a bst? Can someone please explain
We are given the preorder traveral of a BST in the form of an array, We are creating a real BST with the help of that array .
@@ankitbhardwaj7363 okay, so we are making bst from an array..okay thanx
why are we using pointer here ? ,
same thoughts
999k 😊😊😊😊
comment number 100 😕
ghanta malum nhi pad rha kya krr rahi hai ye
😟
GFG :)
@@naveenshah8032 Any other resources bro ? if you found any ? Please share
Didi thora easily samjhaiye na
❤️
Mann i seriously feel that listening to a woman voice for straight 15 min when se speaking continuously and with a high pitch voice is sometimes irritating and difficult..... just my thoughts 😅
Yaar itna ganda koi kaise padha sakta h
🤣😂 ky dikkt ho rha h bta?
Use stack for very small answer. Itna complicated kyu kiye ho