@@honeykumar5700 there is not much difference between preorder and inorder here as the place of print statement of root->val changes in both cases and that is not present here
9:09 One small correction If in question it is mentioned B is always present, then no need to check whether root is NULL or not inside solve funtion. Second thing is if it is not present the array ans is anyways going to be empty. So the code is absolutely correct irrespective of the presence of B.
Bhaiya you mentioned that you are using Inorder but I thinks its preorder. Isn't it? Pardon me if am wrong because in code we are checking root first then moving on to left and right which is clearly a preorder (ROOT, LEFT, RIGHT).
Being, an 27 year old, @striver @takeUforward content is the only highly impacting and really changing lives of people, I saw till now, thanks BRO, love from Sweden, Europe
I believe its inorder because we check the nodes value itself before traversing the left and right nodes. Thats why in the 7 case shown above we directly return true instead of checking left and right
Hi Striver, your videos are awesome but in many videos, there's some confusion between inorder & preorder traversals. Like in this video, you said we will be using inorder (Left, Root, Right) but eventually used preorder (Root, Left, Right).
also dont think it is preorder or something else just see this as we neet root first forget about type of traversals they are not for smart people methods it is like spoon feeding
Best explanation bhaiya, you are indeed a good teacher and our brother. Love ❤ you bhaiya from the bottom of my heart this series is very good and I hope that in future you also achieve great height of success 👍💯.
if (getpath(root->left, arr, B) || getpath(root->right, arr, B)) return true; if getpath(root->left, arr, B) returns True will it traverse through root->right ??
Time Complexity Doubt : Time Complexity should be O(N*H) where N is number of nodes and H is height of tree. Max Length of ArrayList = O(H) Cost of Remove function in ArrayList = O(H) in the worst case, that is when target is rightmost node, we would be checking each node and for removing the elements from arraylist, O(H) time is spent. Hence Time Complexity = O(N*H) Correct me if I am wrong :)
remove will be O(1) because we always remove the last element from array. You can also use a stack instead, then to remove it will require stack.pop() which is O(1)
A more beginner friendly solution that I found: bool path(TreeNode* node, int x, vector &ans) {if(node==NULL) return false; if(node->val==x){ ans.push_back(node->val); return true;} bool find_lc=find(node,x,ans); //find if left child has the value if yes push back value if(find_lc){ ans.push_back(node->val); return true;} bool find_rc=find(node,x,ans); //check for right child if(find_rc){ ans.push_back(node->val); return true;} return false;}
This can also be done using iteration . Create map where we store child asindex and parent as value . Do BFS and fill the map . Then we traverse from node to root using the map and put values in a vector . Reverse the vector and return it .
Nicely explained but I found this one a bit complicated . Because I have solved it without complicating it using stack 😀. Followed your words that we don't need to complicate binary tree problems. Btw thanks for such a wonderful series .
the solution in video is neither inorder nor preorder, we say is DFS. Here is my preorder Solution: bool rec(TreeNode* node, int x, vector &ans){ if(!node) return false; if(node->val == x) return true; if(rec(node->left, x, ans)) { ans.push_back(node->left->val); return true; } if(rec(node->right, x, ans)) { ans.push_back(node->right->val); return true; } return false; } vector Solution::solve(TreeNode* A, int B) { vector ans; rec(A, B, ans); ans.push_back(A->val); reverse(ans.begin(), ans.end()); return ans; }
@takeUforward isn't it preorder traversal, like at every node we are processing it first and then calling the left subtree and right subtree! Anyways thanks for the awesome solution.
you need to also add optimized approaches, iterative in above case, you just make recursive solution videos and in interview we need to come up with optimized approaches as well
I am getting a little confused. Are we implementing in-order or pre-order? At first we are considering the current root, adding it to vector, then we are going to the left and then to the right. I think this is pre order. Please correct me if I am wrong.
@take U forward Sir I was thinking if we pass vector and NOT vector& we would not need to delete a node's value since every node will now have a local copy of this vector and we can return if we find that node else the whole recursion returns just the starting vector (which will be empty)
Came up with this messy code, though this problem was easy enough, striver's videos' just help build logic of next videos(ofc spread across playlists as well) bool hasPath(Node *root, vector& prev, int x) { if(!root)return false; prev.push_back(root->data); if(root->data == x) return true; bool t1 = hasPath(root->left,prev,x); bool t2 = hasPath(root->right,prev,x); // if both subtrees do not have the node, pop the cur root if(!t1 and !t2) prev.pop_back(); else return true; return false;// if subtree does not have the node } // function to print the path from root to the // given node if the node lies in the binary tree void printPath(Node *root, int x) { // vector to store the path vector prev; if (hasPath(root, prev, x)) { for (int i=0; i
My Code: bool getPath(Node* root, int x) { if(root == NULL) return false; path.push_back(root->data); if(root->data == x) return true; bool lh = getPath(root->left, x); if(lh == true) return true; bool rh = getPath(root->right, x); if(rh == true) return true; path.pop_back(); return false; } in striver's code if the left half is already return's true then he'is still going to right half, did you see that if condition if( getPath(root->left, x) || getPath(root->right, x) ) return true; in my code, if we get the left half true, then we're not going any further and directly returning the true.... as always keep posting videos bro... Understood! So fantastic explanation as always, thank you very much!!
Even if node doesn't exist, we don't need to add an extra check since at the end it will return false and finally an empty array. Correct me if I'm wrong 😅
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
@@DeepakKumar-gv3jw no thanks, I don’t accept. Need to care of my body, its not doing well since last few days.
inorder bolke preorder mai solution de diya
@@sixth_sense_working bhai woh toh bass current node ka value check horra hai na.. vaise toh hum inorder hi jaare hain...
@@takeUforward isn't it preorder???
@@honeykumar5700 there is not much difference between preorder and inorder here as the place of print statement of root->val changes in both cases and that is not present here
it was Preorder traversal striver. you are mentioning Inorder. BTW great explanation.
thank you i was doughting my understanding. i was rewatching to understand how is it inorder
Good catch @Shorts_n_Laughs
just amazing like always
You are still the # 1
Greatest of all times (GOT) in algirithm explanations
goat
*GOAT
*ALGORITHM
Bkl GOAT hota h
9:09
One small correction
If in question it is mentioned B is always present, then no need to check whether root is NULL or not inside solve funtion.
Second thing is if it is not present the array ans is anyways going to be empty.
So the code is absolutely correct irrespective of the presence of B.
Bhaiya you mentioned that you are using Inorder but I thinks its preorder. Isn't it? Pardon me if am wrong because in code we are checking root first then moving on to left and right which is clearly a preorder (ROOT, LEFT, RIGHT).
Yes, it's a preorder
Yes Preorder
yes, preorder.
He always say inorder when he mean preorder 😅
Yes its preorder
Will definitely watch your other series as well, so much to learn here.
Greatest of all times (GOT) in algirithm explanations
Another quuestion like this is also pretty cool. Print all paths to leaf nodes.
Understood! So fantastic explanation as always, thank you very much!!
Being, an 27 year old, @striver @takeUforward content is the only highly impacting and really changing lives of people, I saw till now, thanks BRO, love from Sweden, Europe
This is preorder, not inorder
I believe its inorder because we check the nodes value itself before traversing the left and right nodes. Thats why in the 7 case shown above we directly return true instead of checking left and right
@@TechizinHD so preorder means that only we do checking and all before visiting left and right
@@TechizinHD That is called preorder.
Preorder = node left right
InOrder = left node right
PostOrder = left right node
Yeah it's preorder
You are right, in my opinion, Inorder is not possible in traversal, anyhow we have to visit the root before visiting it's left and right
Great explanation but it is a preorder method. striver might have said it inorder by mistake.
Yes...
Good Explanation bro, please bring the DP series also ASAP as placement season has come.
till then watch adi verma
CodeStudio Problem Link: www.codingninjas.com/codestudio/problems/path-in-a-tree_3843990
Leetcode question no. ??????????????????????????
@@adarshgupta2262 257
@@vatsalkudecha2746 no..they are not same
Hi Striver, your videos are awesome but in many videos, there's some confusion between inorder & preorder traversals. Like in this video, you said we will be using inorder (Left, Root, Right) but eventually used preorder (Root, Left, Right).
yeah I'm also having this doubt you know I checked it again and again I thought that I am wrong but later on found that there is some mistake in video
@@imshivendra Yeah even i was confused and checked the comments section and confirmed
@@tarun1200 yup bro
try to ignore his words bhut bar galt bol deta hai pr soln ka feel smjo bhut mst hai
also dont think it is preorder or something else just see this as we neet root first forget about type of traversals they are not for smart people methods it is like spoon feeding
Best explanation bhaiya, you are indeed a good teacher and our brother. Love ❤ you bhaiya from the bottom of my heart this series is very good and I hope that in future you also achieve great height of success 👍💯.
if (getpath(root->left, arr, B) || getpath(root->right, arr, B))
return true;
if getpath(root->left, arr, B) returns True will it traverse through root->right ??
@@devendrapatil07 No
hey...can you please tell...under what name i can find this problem on leetcode?
Waiting for DP series on Diwali.
Thanks for make such awesome videos for free🔥.
G.O.A.T explanation and G.O.A.T presentation bhaiii
Completed 27/54 (50% done) !!!
Time Complexity Doubt : Time Complexity should be O(N*H) where N is number of nodes and H is height of tree.
Max Length of ArrayList = O(H)
Cost of Remove function in ArrayList = O(H)
in the worst case, that is when target is rightmost node, we would be checking each node and for removing the elements from arraylist, O(H) time is spent.
Hence Time Complexity = O(N*H)
Correct me if I am wrong :)
remove will be O(1) because we always remove the last element from array. You can also use a stack instead, then to remove it will require stack.pop() which is O(1)
@@pawansingh7430 Thanks
In gfg you need to find the all leaf node path so just add a extra condition to check leaf node and add in final ans.
A more beginner friendly solution that I found:
bool path(TreeNode* node, int x, vector &ans)
{if(node==NULL) return false;
if(node->val==x){
ans.push_back(node->val);
return true;}
bool find_lc=find(node,x,ans); //find if left child has the value if yes push back value
if(find_lc){
ans.push_back(node->val);
return true;}
bool find_rc=find(node,x,ans); //check for right child
if(find_rc){
ans.push_back(node->val);
return true;}
return false;}
Can u give the question link?
OMG.....Man you are just amazing. Thanks for such insightful and informative content
This can also be done using iteration . Create map where we store child asindex and parent as value . Do BFS and fill the map . Then we traverse from node to root using the map and put values in a vector . Reverse the vector and return it .
looks tedious
Understood
Nicely explained but I found this one a bit complicated . Because I have solved it without complicating it using stack 😀. Followed your words that we don't need to complicate binary tree problems. Btw thanks for such a wonderful series .
I too thought of solving this question using stack.
Can u share the code plz
Recursion uses stack
I think the other approach is do any traversal when we get the node we require then add it to a vector return true and add every parent above.
I think doing simple dfs on the whole tree while maintaining a parent array will do it. The code is much simpler
question link pls??
marvel Explanation
Jzt awesomeeeeeeeeeeeeeeeeeee
you are DronaCharya to every Arjun out there in DSA world !!!
We can go to right first then comeback and then go to left (ROOT, RIGHT, LEFT) I guess this will also work :)
it gets very easy after you see his backtracking vids 🔥🔥
Code For leaf node problem:
void solve(Node *root, vector &ans, vector &temp)
{
if(root==nullptr)
return ;
temp.push_back(root->data);
if(root->left==nullptr and root->right==nullptr)
ans.push_back(temp);
solve(root->left,ans,temp);
solve(root->right,ans,temp);
temp.pop_back();
}
vector Paths(Node* root)
{
// Code here
vector ans;
vector temp;
solve(root, ans, temp);
return ans;
}
superb lecture and concept
Bhaiya how is it In-order traversal, as we r doing root, left, right? Correct me, if i am wrong?
its a preorder traversal,, that was what I was thinking initially. I think he said it by mistake
@@laraibanwar1618 ya He mistakenly said that
the solution in video is neither inorder nor preorder, we say is DFS.
Here is my preorder Solution:
bool rec(TreeNode* node, int x, vector &ans){
if(!node)
return false;
if(node->val == x)
return true;
if(rec(node->left, x, ans))
{
ans.push_back(node->left->val);
return true;
}
if(rec(node->right, x, ans))
{
ans.push_back(node->right->val);
return true;
}
return false;
}
vector Solution::solve(TreeNode* A, int B) {
vector ans;
rec(A, B, ans);
ans.push_back(A->val);
reverse(ans.begin(), ans.end());
return ans;
}
I was also thinking that how the solution in the video can be Inorder as we are processing first root and then left and right
tysm sir
What you explained is not inorder traversal but a preorder traversal
Can u give the question link?
@takeUforward isn't it preorder traversal, like at every node we are processing it first and then calling the left subtree and right subtree! Anyways thanks for the awesome solution.
Day 3 update: Solved two out of three sections of tree.
Goal for day 4: Solve atleast half of difficult tree problems from a2z sheet
Which year 4 year or 3 yr
@@arshmehta50 4
@@sauravchandra10 tum bhi hamari kashti me ho bhai😂
Does it is Pre-Order ?
correct me if I'm wrong
Understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, DUDE
Can u give the question link?
maja agyaa
Hey Striver - You are using a PreOrder traversal
Can someone give me this question link, I can't find it
you need to also add optimized approaches, iterative in above case, you just make recursive solution videos and in interview we need to come up with optimized approaches as well
Thats preorder as u adding value of root then left then right
I am getting a little confused. Are we implementing in-order or pre-order? At first we are considering the current root, adding it to vector, then we are going to the left and then to the right. I think this is pre order. Please correct me if I am wrong.
U r correct.... he said inorder by mistake
PreOrder(root,l,r)
crystal clear explanation
Thank you Bhaiya
bool pathtonode(vector &ans, TreeNode* root,int target){
if(root==nullptr) return false;
ans.push_back(root->val);
if(root->val==target) return true;
if(pathtonode(ans,root->left,target)||pathtonode(ans,root->right,target)) return true;
ans.pop_back(); return false;
} that way is very smart to write thanks
Thank you sir
hi viewer , Its preorder he might be busy so he told it as inorder
we love your content and we love you...🖤
understood
We can return the node and reverse the path at end.
amazing explanation sir
Great explanation as always
Nice work bro bas thoda kaam chillana😅😅
which leetcode question is this i.e., question number
@take U forward Sir I was thinking if we pass vector and NOT vector& we would not need to delete a node's value since every node will now have a local copy of this vector and we can return if we find that node else the whole recursion returns just the starting vector (which will be empty)
if u return vector in main function then it will be empty
Came up with this messy code, though this problem was easy enough, striver's videos' just help build logic of next videos(ofc spread across playlists as well)
bool hasPath(Node *root, vector& prev, int x)
{
if(!root)return false;
prev.push_back(root->data);
if(root->data == x) return true;
bool t1 = hasPath(root->left,prev,x);
bool t2 = hasPath(root->right,prev,x);
// if both subtrees do not have the node, pop the cur root
if(!t1 and !t2) prev.pop_back();
else return true;
return false;// if subtree does not have the node
}
// function to print the path from root to the
// given node if the node lies in the binary tree
void printPath(Node *root, int x)
{
// vector to store the path
vector prev;
if (hasPath(root, prev, x))
{
for (int i=0; i
Good bhai
isnt pre order traversal?
Its a Preorder... But excellent explanation
completed lecture 26 of Tree Playlist.
7:47 wapas
Understood
great!!! could do path sum questions on leetcode with the help of this video
My Code:
bool getPath(Node* root, int x) {
if(root == NULL)
return false;
path.push_back(root->data);
if(root->data == x)
return true;
bool lh = getPath(root->left, x);
if(lh == true)
return true;
bool rh = getPath(root->right, x);
if(rh == true)
return true;
path.pop_back();
return false;
}
in striver's code if the left half is already return's true then he'is still going to right half, did you see that if condition
if( getPath(root->left, x) || getPath(root->right, x) )
return true;
in my code, if we get the left half true, then we're not going any further and directly returning the true....
as always keep posting videos bro... Understood! So fantastic explanation as always, thank you very much!!
You are wrong bro there is or operator in case of or operator if one condition is true then compiler not move forward to check other conditions 😊😊
Even if node doesn't exist, we don't need to add an extra check since at the end it will return false and finally an empty array. Correct me if I'm wrong 😅
Bro then how can we know if node exist or not and than function would not be returning true anymore 🙃
preorder is the easiest, root left right is the easiest.
understood,able to solve by myself
At 9:55
If I had checked for left and right in different if block , would that work , instead of checking them with OR operator ?
how is that inorder ??? isnt it preorder travesal !
Striver 3 should also be added to the array and then popped...right?
Huge respect...❤👏
thanks mate!
Should it be preorder traversal ? 😅
Thankyou striver
Striver is a God and I'm a Dog.
it should be preorder
as in starting we considering the root before traversing to left
can any please elaborate if i am wrong
why didn't we pass the value of given Node in the function pass by reference ??
Root to all nodes problem:-
void path(Node* root, vector& res, vector& ans){
if(root == NULL) return;
res.push_back(root->data);
if(root->left == NULL && root->right == NULL) ans.push_back(res);
if(root->left) path(root->left, res, ans);
if(root->right) path(root->right, res, ans);
res.pop_back();
}
vector Paths(Node* root) {
vector ans;
vector res;
path(root, res, ans);
return ans;
}
Understood 😁
Understood thanks :)
i think it is preorder traversal?
i cant find this question anywhere on any platform
Understood 👍
bhaiya preorder laga rhe ho. inorder nhi. video me change kardo ya description section me p.s likh do
UNDERSTOOD❤
Would this work if we globally define the vector arr and not pass it by reference???
Yes
@@chakravarty-with-a-v thanks
@@mukulupadhyay4656 It is not considered a good practice to define global variables in coding interviews.
p.s. - correct me, if I am wrong.
@@AliAbbas-is2nk Yes
understoood. thanks :)
Bhaiya this solution is in preorder n.....?
Becouse we taking root first then traversing for left and right
understood
poland vale bhaiaaaa ...lit ho
It's preorder traversal
Why it is not preorder? It seems to be preorder to me