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 😊
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
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.
instead of taking an array you can take a public variable 'i' as a data member for class solution and initialise it to 0 remove the third parameter like this class Solution { public int i = 0; public TreeNode bstFromPreorder(int[] preorder) { return bstfropreorder(preorder,Integer.MAX_VALUE); } public TreeNode bstfropreorder(int[] A,int bound){ System.out.println(i); if(i==A.length || A[i]>bound) return null; TreeNode root = new TreeNode(A[i++]); root.left = bstfropreorder(A,root.val); root.right = bstfropreorder(A,bound); return root; } }
@@MANUCRIXZ yes you are absolutely right but in this question I want to show that how you can solve the question by variable(global) instead of an array
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)
@@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.
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 🙂
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); } };
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.
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
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; }
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
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.
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. 😛
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 😂
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
🤣
Striver's way of explaining problems itself solves more than 50% of the problem :)
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.
thank you so much the recursion tree really helped me to understand how return statement is working 🙏
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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.
Amazing solution.
Thank you so much Striver !
instead of taking an array you can take a public variable 'i' as a data member for class solution and initialise it to 0 remove the third parameter like this
class Solution {
public int i = 0;
public TreeNode bstFromPreorder(int[] preorder) {
return bstfropreorder(preorder,Integer.MAX_VALUE);
}
public TreeNode bstfropreorder(int[] A,int bound){
System.out.println(i);
if(i==A.length || A[i]>bound) return null;
TreeNode root = new TreeNode(A[i++]);
root.left = bstfropreorder(A,root.val);
root.right = bstfropreorder(A,bound);
return root;
}
}
not a good approch bcz this approch is taking 11ms runtime where as strivers approch is taking 1ms as runtinne
@@MANUCRIXZ yes you are absolutely right but in this question I want to show that how you can solve the question by variable(global) instead of an array
The upper bound logic is brlliant
9:58 reason why we don't consider lower bound
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.
my mans got a lil conscious about the hair 8:18 🤣🤣🤣. Nice video as usual :)
Loved the explanation
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
Your expressions are so good that you can also go into acting 😆
hello ,Great explanation.We can also solve the problem in O(log N) time complexity by splitting the array in two part left-subtree and right-subtree .
YOu cant man, there are n elements, there is no way you can insert n elements in less than O(n) of time if its not sorted.
Beautiful code!
use stack approach it is very easy
nice 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 🙂
the second method is actually running faster than third one
thank you
Thank you Bhaiya
we love your content and we love you...🖤
5:05 - 8:40 edoc: 14:04
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:
Did this on my own
Can we implement the 3rd method using stack? I think that will be more understandable..
How ?
yes
Mann understod
Thank you so much for providing this series .
SAME JAVA SOLUTION - EASY TO UNDERSTAND 👇
class Solution {
private int index = 0;
private TreeNode helper(int[] preorder, int upper_bound){
if(index==preorder.length || preorder[index]>upper_bound){
return null;
}
TreeNode root = new TreeNode(preorder[index]);
index++;
root.left = helper(preorder, root.val);
root.right = helper(preorder, upper_bound);
return root;
}
public TreeNode bstFromPreorder(int[] preorder) {
return helper(preorder, Integer.MAX_VALUE);
}
}
cant believe you made it so fucking easy. man
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.
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!!
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.
};
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
I really loved your content!!!
understood.
Wat if we have 4 or a 3 after 7 in your example?
understood
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
Why did he make the index a list and not an integer?
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!
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.
In some problems you consider the recursion stack space in the space complexity and in some you don't. Anybody clear this doubt :D, appreciated
Very good explanation of the 3rd method
Can we do another way for all nodes we find their correct postion to insert using bianry search and insert it - O(nlog(H))
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
Video starts at 6:03
why is the code so short
Brute Force Code Below :
TreeNode* bstFromPreorder(vector& pre) {
int n=pre.size();
if(n==0){
return NULL;
}
TreeNode * head=new TreeNode (pre[0]);
for(int i=1;ival>pre[i]){
prev=temp;
temp=temp->left;
}
else{
prev=temp;
temp=temp->right;
}
}
if(prev->val>pre[i]){
prev->left=new TreeNode (pre[i]);
prev=prev->left;
}
else{
prev->right=new TreeNode (pre[i]);
prev=prev->right;
}
}
return head;
}
Can bound be passed by reference?
5:33
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
@@your_name96 can you please explain why it is required i am confused..
Thanks man for wonderful explanation.
why we passed the i by reference ??
because the I value is changing at every iteration, that's why
6:11
understood ,able to solve by myself
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
Here to solve gate 2008 qs :)
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
❤❤
Bro, how many more videos will come of tree topic?
💚
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);
}
}
Great Series
thank you bhaiya!
What an explanation!
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
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
@@AnushkaGupta-x6wexactly this is n^2 solution
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.
BST inorded is always slrted
Thank you sir
done!
understooooood. thanks :)
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😅
US
intuition op!!!
,.......................
"us"
bhai tu pdata bhut bduya hai lekin , ye fake angrzi accent bhut annoying lgta hai , be natural man
noice
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)
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..
Understood
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
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
Done!
Understood
Understood.