Good explaination. But you should also check whether you are at leaf node or not when sum is equal to k. if(sum==k && p->left==NULL && p->right==NULL) then print the stack.
If there are multiple paths, the first one we get will pop all stack contents while printing. How do restore the data in the stack for printing other paths?
//by using this no need to take care of poping and decrement sum void getPath(BTnode* root, stack stk ,int sum , int temp) { if(root==NULL) return; stk.push(root->data); temp = temp+root->data; if(root->left ==NULL and root->right ==NULL) { if(temp==sum) { print(stk); } } getPath(root->left , stk , sum ,temp); getPath(root->right , stk , sum ,temp); }
The paths which don't include roots are not included I think. Please correct me if I am wrong (for example 14), I just saw that it was root to leaf paths,sorry, but could you also provide a code for my problem which doesn't necessarily include root.
Sir what if root node is not there in the required path,i.e. there is a path in left or right sub tree but does not include root? Please reply.Thank u in advance
The question says "root to leaf" path. So we have to include root essentially. The question you're asking is a different one. We have to print the path which includes root for sure.
How about this one without using stack Tree * print_path_with_given_sum(Tree *root, int *sum, int final_sum) { if (root == NULL) return NULL; *sum = *sum + root->element; if (*sum == final_sum) { cout
If anyone is interested in java implementation of above algorithm, please go through the link given below :) leetcode.com/problems/path-sum/discuss/605367/Using-Inorder-traversal-and-stack-In-java
![Height of a Binary Tree / Maximum depth of a binary tree Algorithm [REVISITED]](/img/n.gif)
Its pre-order traversal as the root node is being processed first.
Good explaination.
But you should also check whether you are at leaf node or not when sum is equal to k.
if(sum==k && p->left==NULL && p->right==NULL)
then print the stack.
I thought same
Correct. And also pop the node off the stack and subtract the node value from the sum, so that we can move ahead with other path searches.
@@souravroy4408 That will be automatically done if you ensure the leaf check condition
Sir , Dil se bol rhaa hoon, best explanation. you have so much of knowledge
this is not a Root To Leaf PATH SUM Program... this will generate paths in the tree with a given sum not necessarily root to leaf
interesting to see that you correct your code at 07:46 on the fly ! good job!!!
And it is modified to use Pre-Order traversal of the tree.
Great explanation!
Excellent explanation sir... Tq so much sir....
good explaination sir, i understood your logic well but it's preorder traversal
the traversal that you are doing is definitely preorder ,not inorder
Thank you sir
I think you have to pass the stack reference in the function arguments or else you lose the state of the stack at each recursive function call.
If there are multiple paths, the first one we get will pop all stack contents while printing. How do restore the data in the stack for printing other paths?
Same man. Same.🥺
looking forward more videos like this , ignore negative comments please, great work👌
Great 🙌
May be sum needs to be part of recursive call so that while unwinding we will have previous sum without current node ....
kindly explain complexity in each questions .
This code is not complete. We also need to check if the node is a leaf node , while checking the sum. Thank you for the wonderful explaination.
//by using this no need to take care of poping and decrement sum
void getPath(BTnode* root, stack stk ,int sum , int temp)
{
if(root==NULL)
return;
stk.push(root->data);
temp = temp+root->data;
if(root->left ==NULL and root->right ==NULL)
{
if(temp==sum)
{
print(stk);
}
}
getPath(root->left , stk , sum ,temp);
getPath(root->right , stk , sum ,temp);
}
The paths which don't include roots are not included I think. Please correct me if I am wrong (for example 14), I just saw that it was root to leaf paths,sorry, but could you also provide a code for my problem which doesn't necessarily include root.
Sir what if root node is not there in the required path,i.e. there is a path in left or right sub tree but does not include root?
Please reply.Thank u in advance
The question says "root to leaf" path. So we have to include root essentially. The question you're asking is a different one. We have to print the path which includes root for sure.
@@kumartatsat868 is it necessary that it will end on leaf? sum may be reached before leaf starting from root!
Could you please upload a video, how to return randomNode from a binary search tree?
sir can you upload graph tutorials???Thank you.....
yes very soon..!
Can you show the iterrativ version of this function? Respects.
is this algo also valid for binary search tree ?
I guess, it's not root to leaf path sum problem.
It will generate paths in the tree with a given sum not necessarily root to leaf.
It is root to leaf. But he has to add one condition of leaf node than print the stack.i think..😀🤔
sir could you publish a video on find a largest subtree having identical left and right subtrees
yes veerraju , soon u will see the video..
thank you sir
you are not checking for leaf node condition.this algorithm is not going to work
i will check it rohit...!
lets say we have another node (X) after 10 , then your function will be wrong ..
int add=0;
stackst;
void roottoleaf(node* root,int k)
{
if(root==NULL)
{
return;
}
add=add+(root->data);
st.push(root->data);
if(add==k && root->left==NULL && root->right==NULL)
{
for(int i=0;i
Sir, can you please provide the full code for the algorithm.
LEETCODE #112
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(TreeNode* root, int targetSum,int sum,stack st,bool& ans)
{
if(root==NULL)
{
return;
}
sum+=root->val;
st.push(root->val);
if(sum==targetSum && root->left==NULL && root->right==NULL)
{
ans=true;
}
helper(root->left,targetSum,sum,st,ans);
helper(root->right,targetSum,sum,st,ans);
sum-=root->val;
st.pop();
}
bool hasPathSum(TreeNode* root, int targetSum) {
int sum=0;
stack st;
bool ans=false;
helper(root,targetSum,sum,st,ans);
return ans;
}
};
where to define stack ?? please provide full working code..
Can anyone give me full code of this problem
This is not inorder
How about this one without using stack
Tree * print_path_with_given_sum(Tree *root, int *sum, int final_sum)
{
if (root == NULL)
return NULL;
*sum = *sum + root->element;
if (*sum == final_sum) {
cout
If anyone is interested in java implementation of above algorithm, please go through the link given below :)
leetcode.com/problems/path-sum/discuss/605367/Using-Inorder-traversal-and-stack-In-java
This guy seems to be sleepy.