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 😊
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
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.
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
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)?
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)
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); } };
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 🙂
@@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.
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
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
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.
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.
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??
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
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; }
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
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)
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
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 ☺️
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..
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; }
Please like and share among friends ^ _ ^
Find all links in description!
Thanks a lot striver !! Keep uploading .
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. 😛
The red neon light kind of marker is cool. The way it disappears after every 2 sec😀
no
he makes it disappear look closely
Which app is he using on ipad?
@@saqlainkadiri Goodnotes
@@mritunjay3723 no it disappears after you remove apple pencil from the ipad screen for more than 1 sec . It comes with good notes app
🤣
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 😊
Binod
@@parthsalat 😂
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
recursive stack space is not an external space, thats why its O(1)
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.
thank you so much the recursion tree really helped me to understand how return statement is working 🙏
Striver's way of explaining problems itself solves more than 50% of the problem :)
my mans got a lil conscious about the hair 8:18 🤣🤣🤣. Nice video as usual :)
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
Thanks for this. I really missed this key point.
Loved the explanation
Beautiful code!
Thank you Bhaiya
thank you
The upper bound logic is brlliant
Thank you so much for providing this series .
Your expressions are so good that you can also go into acting 😆
Did this on my own
the second method is actually running faster than third one
understood.
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)?
You are right. I also got this question.
Yeah dfs traversal also takes O(3n) time to be precise but asymptotically it's linear time complexity
for N -> infinity O(3N) is simplified to O(N). So it is linear time complexity.
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)
It should be O(N) only because you can see each recursive function is getting executed only once not thrice.
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
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);
}
};
Exactly, this is what I though of!
understood
9:58 reason why we don't consider lower bound
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:
Can anyone explain why do we need to take array of int rather than just an int value of i ? Thanks !
In java code ?
Because in java, integer can only be passed by value, not by reference
Hope it helps 🙂
cant believe you made it so fucking easy. man
sir for 2nd method (inorder one), I think it should be guarateed that the nodes will be unique otherwise, complexity will increase.
Bst means nodes are unique 😅
@@takeUforward oh ok!! thanks for the clarification!!
Very good explanation of the 3rd method
Thanks man for wonderful explanation.
we love your content and we love you...🖤
Can we implement the 3rd method using stack? I think that will be more understandable..
How ?
yes
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
Can we do another way for all nodes we find their correct postion to insert using bianry search and insert it - O(nlog(H))
Wat if we have 4 or a 3 after 7 in your example?
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 🙂
why did we use reference? why is it not working without reference?
@@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 :)
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.
};
I really loved your content!!!
Can someone elaborate why the java code fails when we pass a variable instead or array in this case?? plz
Because java does not support call by address.
Here to solve gate 2008 qs :)
can someone tell Why is variable i passed by reference??
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
@@sushmitaraj6948 but we can also use pass by value right...because we're increasing the i value before passing it
Can bound be passed by reference?
Why did he make the index a list and not an integer?
understood ,able to solve by myself
Great Series
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 ) .
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
@@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.
why is the code so short
5:05 - 8:40 edoc: 14:04
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
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;
}
};
hey how did you think of this solution can you provide me the thought process or intuition pls
What an explanation!
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
Same. Did you figure it out?
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.
u need to pass the index as reference or declare it as a global variable
understooooood. thanks :)
thank you bhaiya!
Bro, how many more videos will come of tree topic?
why we passed the i by reference ??
because the I value is changing at every iteration, that's why
5:33
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.
6:11
Video starts at 6:03
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??
cheers!, I just thought the same way,
guess the TC is still O(n)
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
@@user-qq5bb7bh5zexactly this is n^2 solution
done!
Iska time complexity smjh mein ni aya
Backtracking ke liye alag se O(n) kiu le rahe ho
kon sa 1st or 2nd or 3rd?
@@CHANDANKUMAR-sg8cp 3rd
BST inorded is always slrted
Thank you sir
💚
Understood
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);
}
}
,.......................
Method 3 samjh nhi aaya - tried 3 baar 😢
pen paper pe dry run krke dekho, ayega samaj me
@@anshumaan1024 yes i tried and got it
but ig i still need more practice😅
I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?
Ofcourse it is enough
practice on ur own also buddy, not everything will be served to u!
You need to drop out of college for getting into tech giants
Done!
intuition op!!!
Understood.
noice
❤❤
"us"
US
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
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)
bhai tu pdata bhut bduya hai lekin , ye fake angrzi accent bhut annoying lgta hai , be natural man
Next Video on Clarification about CP vs Development
No already available bhai fltu videos ki demand q krte ho...ye sab Babbar Vagairah se kro
It will not work if pre Oder is 100 200 20 80 50 60 40 10
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
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 ☺️
Nah nah, its the confience that i have covered in the previous videos.. haha thanks man..
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..
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;
}
understood
Understood