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.
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); } };
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; } }
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 🙂
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
@@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.
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.
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
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)
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..
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
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 😂
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.
Striver's way of explaining problems itself solves more than 50% of the problem :)
thank you so much the recursion tree really helped me to understand how return statement is working 🙏
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.
The upper bound logic is brlliant
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
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 🙂
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!!
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!
Your expressions are so good that you can also go into acting 😆
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:
the second method is actually running faster than third one
9:58 reason why we don't consider lower bound
Loved the explanation
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;
}
}
nice solution
Can we implement the 3rd method using stack? I think that will be more understandable..
How ?
yes
Beautiful code!
my mans got a lil conscious about the hair 8:18 🤣🤣🤣. Nice video as usual :)
thank you
Did this on my own
Thank you Bhaiya
cant believe you made it so fucking easy. man
we love your content and we love you...🖤
Thank you so much for providing this series .
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
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.
};
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 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.
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
Can we do another way for all nodes we find their correct postion to insert using bianry search and insert it - O(nlog(H))
understood
understood.
Wat if we have 4 or a 3 after 7 in your example?
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
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
Very good explanation of the 3rd method
Thanks man for wonderful explanation.
Why did he make the index a list and not an integer?
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.
understood ,able to solve by myself
I really loved your content!!!
Can bound be passed by reference?
5:05 - 8:40 edoc: 14:04
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);
}
}
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
Great Series
Here to solve gate 2008 qs :)
What an explanation!
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.
Thank you sir
why we passed the i by reference ??
because the I value is changing at every iteration, that's why
why is the code so short
thank you bhaiya!
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);
}
}
understooooood. thanks :)
Bro, how many more videos will come of tree topic?
done!
intuition op!!!
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
Understood.
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
5:33
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
💚
Video starts at 6:03
6:11
US
❤❤
noice
,.......................
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😅
bhai tu pdata bhut bduya hai lekin , ye fake angrzi accent bhut annoying lgta hai , be natural man
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)
"us"
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..
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
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