For the people who are saying that in line 16 it should be "if" instead of "else if", actually "else if" is fine because in this condition any one of the children in left and right will be made equal to the root->val so it will eventually serve the purpose, as the sum will now automatically be bigger than the root->val as one of the child is equal to root->val.
Self Notes 📜: 🥥 if both children sum is less than parent, make children's value to parent's value. 🥥 if both children values sum is greater than or equal to parent, make parent's value to children's sum. 🥥 recursively go left and right. Traversal type: DFS. 🥥 when coming back up the tree, take children sum and replace it in parent. 🥥 at any point we reach null, just return (base case) 🥥 Intuition: while going down, increase the children values so we make sure to never fall short, then all we have to do is sum both children and replace it in parent.
hey i have a doubt, anyone can pls reply to it. pt-2 - if both children values sum is greater than or equal to parent, make parent's value to children's sum. so here when why we make this. As anyways while returning back to sum, we will simply do sum and replace parent, so why this step?? PLEASE TELL
@@balakrishnanr648 there may be a chance that you get higher value in parent than the total sum value of its both child to avoid this we have to continuously increase the childs value because we can't decrease the value we can only increase the value
@@balakrishnanr648 You are correct....that step is not required.....anyways it will change the value of root after returning..no need to change it beforehand.....
An important optimization: We don't need to consider the case where child>=root->data. We only need to consider the case where childdata and increase the value of child to root->data. The optimized code: void changeTree(BinaryTreeNode < int > * root) { if(root==NULL) return; int child=0;
if(root->left) child+=root->left->data; if(root->right) child+=root->right->data; //we make sure that while going down the child has no shortage if(child < root->data) { if(root->left) { root->left->data=root->data; } if(root->right) { root->right->data=root->data; } } changeTree(root->left); changeTree(root->right); //while going back up int tot=0; if(root->left) tot+=root->left->data; if(root->right) tot+=root->right->data;
Thanks, Striver for the explanation you are making our lives very easy with your hard work. I think that else in 16 line is not required just if is enough
Haina.... Cause if child value is less then we are updating the values of *both* the children if they are *present* to root value. Thanx for the confirmation. Striver your existence itself is a blessing man ♥️🔥
You're right. But think about why we are updating child nodes. We are doing it, so that SUM of child nodes becomes greater than or equal to the parent node. Now if you update both children to parent's value (say x), while returning from function call, parent would be updated to SUM of child nodes, right? Means, 2x. However, if like striver, you use if and else, only one of the node will have the value x. The other will be having a value smaller than x. Their SUM will be < 2x. This will help *prevent integer overflow*
even line #13 is not needed na? why update root = left+right while traversing down the tree? anyway this operation will happen when we're coming back up. right?
In line 14 inside the else block, in the explanation, you were saying that assigns the value of root node to both the children but in the code, the root value is being assigned to either left or right child. According to explanation it should be like, if(root->left) root->left->data=root->data; if(root->right) root->right->data=root->data;
@@krishnavamsichinnapareddy It's not a mistake. Think about it all we need is that root node should not be greater than the sum of it's children. Even if we make any one equal to root node our problem will be solved.
Its not required to even make it equal to the root value....we can just get the difference of both and add that difference to any one of the node....and it will make sure that the sum of both the child is equal to root value....
what would be the approach is the qs is- 1. Convert to childrenSum, with minimum no. of nodes changed 2. Convert to childrenSum, with minimum value added to all nodes cumulatively.
I have developed a method by myself. Make root->data as INT_MAX. Their children should be INT_MAX/2 and so on. if one of children greater than INT_MAX/2 just make the other child as parent->data-child1->data. Now recurse. This works because the cases take care of the fact that the sum of the children never goes beyond INT_MAX for all levels.
ya it's nice approach , but while backtracking pls also update nodes , because diving by 2 can lead to zero in some edge cases , due to which might summation at top node will differ
What if I first check the maximum element in the whole tree, then assign that value to every leaf node and sum them to their parents. That will also solve the question in linear time
@@Rajesh-op8zx Not necessarily, instead of finding maximum element overall, you can just find the maximum value encountered till now, pass by reference, and keep updating, this way you don't need any additional traversal. a leaf node can have any value provided it is greater than all its ancestors. then we can fix the parents as equal to sum of children.
@@abhishekseth5852 keeping track of the parent node's value, he eliminated the lines 5-17 evaluation using that, but in interview it become more difficult to explain this kind of code.
In line 14 inside the else block, in the explanation you were saying that assign the value of root node to both the children but in the code the root value is being assign to either left or right child. I am really confused why is it so, according to explanation it should be like, if(root->left) root->left->data=root->data; if(root->right) root->right->data=root->data;
The code shown in the video is also correct, our main goal is to make sure that we do not need to subtract anything from the root. Increasing any one of the child nodes to the root value will do the job
i thought of a different approach! like find the maximum value in the tree, keep assigning and incrementing that value increasing order bottom to up, makes it in O(N) and pretty straight forward ig! but it will need 2 traversals to get it done...
I think line 13 is not required. We can just check for child < root->data. Why line 13 is not required because after completing left and right recursion we will be adding left and right children values and update that value to root. Am I correct ?
The case when the sum of left and right child is greater than the parent node, there is no need to update the parent node , because the value of nodes can only be increased or remain constant and in either of the cases the parent node's value would for sure be lesser than the sum of children. Correct me if I'm wrong, and also mention the case where you find it fails
NOT Recursive Soln, since data on nodes are >= 1 given int the test case, so when sum is 0 I did continue Just a simple level order traversal int isSumProperty(Node *root) { // Add your code here queue q; q.push(root); while(!q.empty()){ int n = q.size(); for(int i = 0;i < n;i++){ int sum = 0; Node* node = q.front(); q.pop(); if(node->left){ q.push(node->left); sum+=node->left->data; } if(node->right){ q.push(node->right); sum+=node->right->data; } if(sum == 0) continue; if(node->data != sum) return false; } } return true; }
kindly make a video on this, where it is asked to find a binary tree as minimum as possible. I guess the interviewer might ask if we directly approach to O(n), then might change the qs to minimize the binary tree. thank you.
can we find the max value in a tree and then update the tree leaf nodes with this max value and while returning add the child nodes' values to the parent nodes 🤔🤔, the flaw I guess may be stack overflow but for smaller constraints, this soln can be used?
**This is the basic approach which takes O(N) time complexity.** int solve(Node *root){ if(!root) return 0; if(!root->left && !root->right) return root->data; int left = solve(root->left); int right = solve(root->right); if(left == -1 || right == -1) return -1; if(left + right != root->data) return -1; return root->data;
} int isSumProperty(Node *root) { // Add your code here if(solve(root) == -1) return 0; return 1; }
what if the maximum value in the BT is the maximum value accepted by C++? This will lead to overflow right? I think for loose constraints this will work.
Got confused!!! I thought the video was for checking if the tree is having children sum property. Please change the title to "Convert binary tree to children sum tree", otherwise it's misleading.
This question can be done like this ki take maximum of the tree and allow all the leaf nodes to be take the maximum value and then start updating the values from the leaf nodes.
## Easy Approach 1.queue ds taken to check every node 2.check if leftdata and rightdata is there are not. 3.if there --> addded else not equal to means return 0; 4.to check every node add leftnode and right node ---------------just like level orderr----------------------------------------- public static int isSumProperty(Node root) { Queue q=new LinkedList(); q.add(root); while(!q.isEmpty()){ Node node=q.poll(); int leftdata=(node.left!=null) ? node.left.data : 0; int rightdata=(node.right!=null) ? node.right.data : 0; if(node.left!=null || node.right!=null){ if(node.data!=leftdata+rightdata) return 0; } if(node.left!=null) q.add(node.left); if(node.right!=null) q.add(node.right); } return 1; }
Intuition(According to striver): As we go down we need to increase the node values ,so that whenever we recursively return back we will experience no shortage. public class Solution { public static int getAns(BinaryTreeNode root){ if(root==null){ return 0; } if(root.left ==null && root.right ==null){ return root.data; } int left_val=root.left!=null?root.left.data:0; int righ_val=root.right!= null?root.right.data:0; if(left_val+righ_val root) { getAns(root); } }
int postorder(Node* node, int parent) { if (!node) return 0; // if parent's value is greater than me then increase my value // because I can always increase parent's value but not decrease it node->val = max(node->val, parent); int left = postorder(node->left, node->val); int right = postorder(node->right, node->val); // if the sum of my child values is greater than me then increase my value to their sum if (node->val < left + right) { node->val = left + right; } // return my value to the parent so that parent can increase it's value if needed return node->val; } // caller method int main() { postorder(root, INT_MIN); }
@@takeUforward thank you bhaiya for replying. actually maine isliye comment kiya ki agar kisi aur ko aisa doubt aaye to wo confirm ho jaaye ki wo shi hai.😄
in line 25, is this compulsory to write this condition for leaf node? or we can simply assign value tot into node, because for leaf node tot will automatically remains 0, so I does not matter
but still there will be out of bound case right. what if the root value is INT_MAX-1: and you assign same value to its children? while adding these can go out of bound right? please let me know if i am missing something?
just a recursive post order traversal needed function Childrensum(root) { let validroot = isLeaf(root); if (validroot) return; Childrensum(root.left); Childrensum(root.right); let childrensum = 0; if (root.left) childrensum += root.left.data; if (root.right) childrensum += root.right.data; if (root.data > childrensum) root.left += root.data - childrensum; else if (root.data < childrensum) root.data = childrensum; return root; }
I have one doubt, In an interview how to come up with a test case which is best for explanation, Because sometimes random test case cannot cover edge cases. Do we also need to mug up the test cases. Please reply.....
int ch(struct node * root,int m) { if(root==NULL) return 0; if(root->left==NULL&&root->right==NULL) { root->data=max(root->data,m); return root->data; } int l=ch(root->left,max(m,root->data)); int r=ch(root->right,max(m,root->data)); root->data=l+r; return root->data; } "We update each leaf node with the maximum value encountered along the root-to-leaf path to ensure that no node on this path holds a value lower than the maximum encountered so far. For, non-leaf we then compute the sum of their children's values and replace the parent's value with this sum."
Why we are changing the root Node, when Child node is greater than Parent Node. I think, This we can ignore. Because at the end , we are checking Root value.. I think, this Part can be ignored if(child>=root->data? root->data=child).
@@ajiteshsaxena6015 yaa u r right too but even if we do simply if for both...like change both left nd right then also the code will be correct , right ??
sir, when the sum of children > node, I think it is feasible to just assign nodes value to left and right and add them up while backtracking(same as what u did for sum of children < node). What i mean to say is just give the node's value to the children and add them up while backtracking. Is it correct??
@@Yash-uk8ib i think approach stated by you fails when for example you have node value as 45 and its children values are say (50,30). in this case 50+30 > node . But we cannot just assign 45 to a child which is containing 30 as it cannot be decreased. Correct me if I understood this wrong.
@@saikrishnalanka133 u r correct, but I meant that just flood up every node with a greater value so while backtracking u just have to add them, no need to check greater or smaller
this is wrong right? why is there an else if if (root->left) { root->left->val = root->val; } else if (root->right) { root->right->val = root->val; } it should be both if's only
in this contion we have to increase always , but the constrain you are talking about, we can do this question with same approach without writing 13 line and above stuff , there never overflow will occur.
// go left then go right reorder(root->left); reorder(root->right);
// while coming back int total = 0; if(root->left){ total+=root->left->data; } if(root->right){ total+=root->right->data; } // just check if any one of left or right exists if(root->left || root->right){ root->data=total; } }
Level Order Traversal can solve it as well and with much better intuition int isSumProperty(Node *root) { queue q; q.push(root); while(!q.empty()){ Node* node = q.front(); q.pop(); int left = 0; int right = 0; if(node->left){ left+=node->left->data; q.push(node->left); } if(node->right){ right+=node->right->data; q.push(node->right); } if(left+right != 0 && left+right != node->data){ return 0; } } return 1; } => we check left + right != 0 to consider that leaf nodes cannot have a child.
@@jatinchoubey6053 we reassign the values to left and right children because we want the sum to be greater than the root node. Hence, striver assigned both the children values to the root node only. We can also just assign any one of the children values to root value as the sum of this child's value and the other child's value (which is always positive) will anyways be greater than the root node
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
bhaiya what will happen if the root node is 2 and rest of the childrens are higher than 2 just like in 1 question of the video
@@yashdubeyofficial so we have to change the value of root by the sum of the left and right child
In line 16 of both the codes it will only be if not else if
GOAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAT
okkkkkkkkkkkkkkkkkkkkkkkkkk:)
For the people who are saying that in line 16 it should be "if" instead of "else if", actually "else if" is fine because in this condition any one of the children in left and right will be made equal to the root->val so it will eventually serve the purpose, as the sum will now automatically be bigger than the root->val as one of the child is equal to root->val.
will not work if negative value exists
i have a doubt in this because when if condition is satisfied why it will go to else if statement
Self Notes 📜:
🥥 if both children sum is less than parent, make children's value to parent's value.
🥥 if both children values sum is greater than or equal to parent, make parent's value to children's sum.
🥥 recursively go left and right. Traversal type: DFS.
🥥 when coming back up the tree, take children sum and replace it in parent.
🥥 at any point we reach null, just return (base case)
🥥 Intuition: while going down, increase the children values so we make sure to never fall short, then all we have to do is sum both children and replace it in parent.
Thank you!!
hey i have a doubt, anyone can pls reply to it.
pt-2 - if both children values sum is greater than or equal to parent, make parent's value to children's sum.
so here when why we make this.
As anyways while returning back to sum, we will simply do sum and replace parent, so why this step??
PLEASE TELL
@@balakrishnanr648 I have same doubt , I submitted on codestudio without this condition and my soln was accepted .
@@balakrishnanr648 there may be a chance that you get higher value in parent than the total sum value of its both child to avoid this we have to continuously increase the childs value because we can't decrease the value we can only increase the value
@@balakrishnanr648 You are correct....that step is not required.....anyways it will change the value of root after returning..no need to change it beforehand.....
An important optimization:
We don't need to consider the case where child>=root->data.
We only need to consider the case where childdata and increase the value of child to root->data.
The optimized code:
void changeTree(BinaryTreeNode < int > * root) {
if(root==NULL)
return;
int child=0;
if(root->left)
child+=root->left->data;
if(root->right)
child+=root->right->data;
//we make sure that while going down the child has no shortage
if(child < root->data)
{
if(root->left)
{
root->left->data=root->data;
}
if(root->right)
{
root->right->data=root->data;
}
}
changeTree(root->left);
changeTree(root->right);
//while going back up
int tot=0;
if(root->left)
tot+=root->left->data;
if(root->right)
tot+=root->right->data;
if(root->left || root->right)
root->data=tot;
}
Thank you
Line 19 and 20 in C++ code should be calling the same function so it should be changeTree instead of reorder
Yes
yes broo
yeah , that was wierd.
Thanks bro, even I got the same doubt, from where the hell did that reorder function come.
Genious. I have implemented it in O(n^2) but never thought it could be done in O(n). Thanks a lot
O(n^2) approach
Thanks, Striver for the explanation you are making our lives very easy with your hard work.
I think that else in 16 line is not required just if is enough
Haina.... Cause if child value is less then we are updating the values of *both* the children if they are *present* to root value.
Thanx for the confirmation.
Striver your existence itself is a blessing man ♥️🔥
You're right.
But think about why we are updating child nodes. We are doing it, so that SUM of child nodes becomes greater than or equal to the parent node.
Now if you update both children to parent's value (say x), while returning from function call, parent would be updated to SUM of child nodes, right? Means, 2x.
However, if like striver, you use if and else, only one of the node will have the value x. The other will be having a value smaller than x. Their SUM will be < 2x.
This will help *prevent integer overflow*
even line #13 is not needed na?
why update root = left+right while traversing down the tree?
anyway this operation will happen when we're coming back up.
right?
Greatest DSA content by a big margin!!
Before knowing O(n), you should tell the students Brute force then O(N^2) and then teach O(N)
Don't be bothered
ayo rustagi bhaiya how're you?
your twitter follower here!
I was also going to comment the same
Weakling spotted
In line 14 inside the else block, in the explanation, you were saying that assigns the value of root node to both the children but in the code, the root value is being assigned to either left or right child. According to explanation it should be like,
if(root->left)
root->left->data=root->data;
if(root->right)
root->right->data=root->data;
i think its just a mistake.
yeah right buddy
Yeah may be silly mistake in the code
@@krishnavamsichinnapareddy It's not a mistake. Think about it all we need is that root node should not be greater than the sum of it's children. Even if we make any one equal to root node our problem will be solved.
Its not required to even make it equal to the root value....we can just get the difference of both and add that difference to any one of the node....and it will make sure that the sum of both the child is equal to root value....
what would be the approach is the qs is-
1. Convert to childrenSum, with minimum no. of nodes changed
2. Convert to childrenSum, with minimum value added to all nodes cumulatively.
Ask Chatgpt
I have developed a method by myself. Make root->data as INT_MAX. Their children should be INT_MAX/2 and so on. if one of children greater than INT_MAX/2 just make the other child as parent->data-child1->data. Now recurse. This works because the cases take care of the fact that the sum of the children never goes beyond INT_MAX for all levels.
Sounds great. Do you have the code?
ya it's nice approach , but while backtracking pls also update nodes , because diving by 2 can lead to zero in some edge cases , due to which might summation at top node will differ
What if I first check the maximum element in the whole tree, then assign that value to every leaf node and sum them to their parents. That will also solve the question in linear time
Yes does that.
Yes that can be done, but it has a higher chance of resulting in overflow for large values.
@@srishtigupta9516 plus finding maximum element itself requires 1 more travesal
@@Rajesh-op8zx Not necessarily, instead of finding maximum element overall, you can just find the maximum value encountered till now, pass by reference, and keep updating, this way you don't need any additional traversal.
a leaf node can have any value provided it is greater than all its ancestors. then we can fix the parents as equal to sum of children.
@@shikharsharma3980 I think videos approach is little complex but finding max then go ahead is little easy What you think about that bro .
int fun(BinaryTreeNode < int > * root,int par)
{
if(!root)
return 0;
int l=fun(root->left,max(root->data,par));
int r=fun(root->right,max(root->data,par));
root->data=max(l+r,max(root->data,par));
return root->data;
}
void changeTree(BinaryTreeNode < int > * root) {
fun(root,0);
}
Nice Aman bro
didn't get it, why u used par?
@@abhishekseth5852 keeping track of the parent node's value, he eliminated the lines 5-17 evaluation using that, but in interview it become more difficult to explain this kind of code.
@@your_name96 but it is very clean following the approach.
@@your_name96 can u provide the ques link?????
In line 14 inside the else block, in the explanation you were saying that assign the value of root node to both the children but in the code the root value is being assign to either left or right child. I am really confused why is it so, according to explanation it should be like,
if(root->left)
root->left->data=root->data;
if(root->right)
root->right->data=root->data;
yes man, You are right
yes i think its typo
Yeah
The code shown in the video is also correct, our main goal is to make sure that we do not need to subtract anything from the root. Increasing any one of the child nodes to the root value will do the job
@@shikhar2k01 no,if root->right is -ve ,their addition will be less than root->data.
Understood.
BTW, i feel like the problem title should be "Convert binary tree to children sum tree"
Okay let me change
Understood..........Simply Amazing ... loved the approach. You are generous.
i thought of a different approach! like find the maximum value in the tree, keep assigning and incrementing that value increasing order bottom to up, makes it in O(N) and pretty straight forward ig! but it will need 2 traversals to get it done...
I like this approach. Thanks for posting 🙌🏻
Typo in line 19 and 20 of CPP code
Striver bhai pk ho kya yr aap..
Line 19 or 20 me reorder call kar diya mtlb kuch bhi ho rha hai..
Wese explain bhut mst kiya tha love you..❣️
excellent approach. just blew my mind away. How to do this question if we needed sum to be as minimized as possible?
Bhaiya ek minor mistake h code m reorder(root->left) ki jgh changeTree() ayega. Happy Learning. Thankyou for amazing content.
I think line 13 is not required. We can just check for child < root->data.
Why line 13 is not required because after completing left and right recursion we will be adding left and right children values and update that value to root. Am I correct ?
Not able to find the exact same question on any coding platform, Anyone help plz
Which Platform does have this question?
Understood! So awesome explanation as always, thank you very much!!
The case when the sum of left and right child is greater than the parent node, there is no need to update the parent node , because the value of nodes can only be increased or remain constant and in either of the cases the parent node's value would for sure be lesser than the sum of children.
Correct me if I'm wrong, and also mention the case where you find it fails
NOT Recursive Soln,
since data on nodes are >= 1 given int the test case, so when sum is 0 I did continue
Just a simple level order traversal
int isSumProperty(Node *root)
{
// Add your code here
queue q;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i = 0;i < n;i++){
int sum = 0;
Node* node = q.front();
q.pop();
if(node->left){
q.push(node->left);
sum+=node->left->data;
}
if(node->right){
q.push(node->right);
sum+=node->right->data;
}
if(sum == 0) continue;
if(node->data != sum) return false;
}
}
return true;
}
kindly make a video on this, where it is asked to find a binary tree as minimum as possible.
I guess the interviewer might ask if we directly approach to O(n), then might change the qs to minimize the binary tree.
thank you.
Did you mean minimise the increments?
can somebody post the question link
pretty hard for me not just this question but actually whole tree datastructure.
such a easy to understand and easy to code solution and explanation for this question
yes line 13 is not required on coming back from recursion we will handle that.
can we find the max value in a tree and then update the tree leaf nodes with this max value and while returning add the child nodes' values to the parent nodes 🤔🤔, the flaw I guess may be stack overflow but for smaller constraints, this soln can be used?
There shouldn't be stack overflow since it's just a recursive DFS traversal, but it could probably lead to integer overflow.
yeah u correct that works as well
in which plateform we can solve this problem
I got myself the answer in just 10 mins O(n) after solving 30+ tree qs :)
**This is the basic approach which takes O(N) time complexity.**
int solve(Node *root){
if(!root) return 0;
if(!root->left && !root->right) return root->data;
int left = solve(root->left);
int right = solve(root->right);
if(left == -1 || right == -1) return -1;
if(left + right != root->data) return -1;
return root->data;
}
int isSumProperty(Node *root)
{
// Add your code here
if(solve(root) == -1) return 0;
return 1;
}
This problem is very vague , also without constraints this approach may exceed long long.
What if all the values are negative. In that case the solution won’t work as adding two negative child number is decreasing the root value.?
what if the maximum value in the BT is the maximum value accepted by C++? This will lead to overflow right? I think for loose constraints this will work.
Got confused!!! I thought the video was for checking if the tree is having children sum property. Please change the title to "Convert binary tree to children sum tree", otherwise it's misleading.
This question can be done like this ki take maximum of the tree and allow all the leaf nodes to be take the maximum value and then start updating the values from the leaf nodes.
i am not getting to solve this question the link follows some other question
where is the question link ???
Really auesome
if you provide the problem link it will be more helpful.. can you please ????
## Easy Approach
1.queue ds taken to check every node
2.check if leftdata and rightdata is there are not.
3.if there --> addded
else not equal to means return 0;
4.to check every node add leftnode and right node
---------------just like level orderr-----------------------------------------
public static int isSumProperty(Node root)
{
Queue q=new LinkedList();
q.add(root);
while(!q.isEmpty()){
Node node=q.poll();
int leftdata=(node.left!=null) ? node.left.data : 0;
int rightdata=(node.right!=null) ? node.right.data : 0;
if(node.left!=null || node.right!=null){
if(node.data!=leftdata+rightdata) return 0;
}
if(node.left!=null) q.add(node.left);
if(node.right!=null) q.add(node.right);
}
return 1;
}
5:55 - 6:30
eDoC: 13:10
Huge Respect Bhaiyya..❤👏
what if it is minimum kind of question ?
will it throw error when root node is INT_MAX?
Self note:
line no 13 redundant...since while coming back root will be assigned as sum of children
Intuition(According to striver):
As we go down we need to increase the node values ,so that whenever we recursively return back we will experience no shortage.
public class Solution {
public static int getAns(BinaryTreeNode root){
if(root==null){
return 0;
}
if(root.left ==null && root.right ==null){
return root.data;
}
int left_val=root.left!=null?root.left.data:0;
int righ_val=root.right!= null?root.right.data:0;
if(left_val+righ_val root) {
getAns(root);
}
}
Another approach O(N):-
void changeTree(Node*&root,int maxi){
if(!root)return;
if(!root->left&&!root->right){root->data=maxi;return;}
helper(root->left,maxi);
helper(root->right,maxi);
int val=0;
if(root->left)val+=root->left->data;
if(root->right)val+=root->right->data;
root->data=val;
return;
}
void maxvalue(Node*root,int &maxi){
if(!root)return;
maxi=max(maxi,root->data);
maxvalue(root->left,maxi);
maxvalue(root->right,maxi);
return;
}
Bro,remove else at line no 16,then correct result will be achieved
can anyone share the link of gfg which has O(n^2) soution?
int postorder(Node* node, int parent) {
if (!node) return 0;
// if parent's value is greater than me then increase my value
// because I can always increase parent's value but not decrease it
node->val = max(node->val, parent);
int left = postorder(node->left, node->val);
int right = postorder(node->right, node->val);
// if the sum of my child values is greater than me then increase my value to their sum
if (node->val < left + right) {
node->val = left + right;
}
// return my value to the parent so that parent can increase it's value if needed
return node->val;
}
// caller method
int main() {
postorder(root, INT_MIN);
}
awesome!
there is no need of 13th line in cpp code
Yeah we can ignore that, realised later.
@@takeUforward thank you bhaiya for replying. actually maine isliye comment kiya ki agar kisi aur ko aisa doubt aaye to wo confirm ho jaaye ki wo shi hai.😄
return (root->val == root->left->val + root->right->val);
I solved it in a single line
Hackerman
what if we assign 0 to every node??
Thank you for all your videos, awesome explanation
in line 25, is this compulsory to write this condition for leaf node? or we can simply assign value tot into node, because for leaf node tot will automatically remains 0, so I does not matter
if we remove the if statement, the leaf nodes will become 0.
what is that reorder at line no. 19 and 20 it should be changeTree na ?
yea it is a typo
GOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOAT
UNDERSTOOD;
but still there will be out of bound case right.
what if the root value is INT_MAX-1:
and you assign same value to its children? while adding these can go out of bound right?
please let me know if i am missing something?
there are multiple syntax error in this code , it WILL NOT run on compiler
Why all leaves of Binary Tree not holding same value for 1st test-case you took ?
instead of just copying the root element to the child, can we take half of that and do the rest part same?
will it work?
just a recursive post order traversal needed
function Childrensum(root) {
let validroot = isLeaf(root);
if (validroot) return;
Childrensum(root.left);
Childrensum(root.right);
let childrensum = 0;
if (root.left) childrensum += root.left.data;
if (root.right) childrensum += root.right.data;
if (root.data > childrensum) root.left += root.data - childrensum;
else if (root.data < childrensum) root.data = childrensum;
return root;
}
we love your content and we love you.....🖤
What a nice solution sirji!!
I have one doubt, In an interview how to come up with a test case which is best for explanation, Because sometimes random test case cannot cover edge cases. Do we also need to mug up the test cases. Please reply.....
Given N < 100, and if it is a skewed tree from leaf node it will calculate like 2*2*2*.... which will become very large, am i right or wrong?
else if at line 16 is not required. only if suffice
int ch(struct node * root,int m)
{
if(root==NULL)
return 0;
if(root->left==NULL&&root->right==NULL)
{
root->data=max(root->data,m);
return root->data;
}
int l=ch(root->left,max(m,root->data));
int r=ch(root->right,max(m,root->data));
root->data=l+r;
return root->data;
}
"We update each leaf node with the maximum value encountered along the root-to-leaf path to ensure that no node on this path holds a value lower than the maximum encountered so far. For, non-leaf we then compute the sum of their children's values and replace the parent's value with this sum."
Why we are changing the root Node, when Child node is greater than Parent Node. I think, This we can ignore. Because at the end , we are checking Root value..
I think, this Part can be ignored
if(child>=root->data? root->data=child).
Yes, you are right.
line 16 is wrongly typed
it should be "if" instead of "else if"
NO!! It is correct because changing value of only one child make the sum of child nodes greater than parent node.
@@ajiteshsaxena6015 But in the video itself we changed both the values of right and left
@@ajiteshsaxena6015 yaa u r right too but even if we do simply if for both...like change both left nd right then also the code will be correct , right ??
Why does the code looks so easy after seeing but when i try by self i go blank😭😭😭
can anyone explain why should we update parent sum with children's sum if parent sum is less than children sum before recursive call.
sir, when the sum of children > node, I think it is feasible to just assign nodes value to left and right and add them up while backtracking(same as what u did for sum of children < node). What i mean to say is just give the node's value to the children and add them up while backtracking. Is it correct??
Yess
@@takeUforward thanku sir
@@Yash-uk8ib i think approach stated by you fails when for example you have node value as 45 and its children values are say (50,30). in this case 50+30 > node . But we cannot just assign 45 to a child which is containing 30 as it cannot be decreased. Correct me if I understood this wrong.
@@saikrishnalanka133 u r correct, but I meant that just flood up every node with a greater value so while backtracking u just have to add them, no need to check greater or smaller
why cant we make every node value 0 ??
we can't decrease the node value. thats why
Brilliant!
Bhayya can't it be done without adding left and right if childsum> root to the root
i.e if block Bcz i think it can work
Thank you so much !
this is wrong right? why is there an else if
if (root->left) {
root->left->val = root->val;
} else if (root->right) {
root->right->val = root->val;
}
it should be both if's only
line 16 i think instead of else if it should be only if
Yeah that also works
where is the link for this question?
won't it overflow when max element is big and number of nodes is upto 2e5?
in this contion we have to increase always , but the constrain you are talking about, we can do this question with same approach without writing 13 line and above stuff , there never overflow will occur.
wow
can any one explain how the space complexity is O(N)?? please...
Yo yo yo Striver Bhaiya rocks
Self Explainatory CPP code:
void reorder(BinaryTreeNode < int > * root){
if(root==NULL){
return;
}
int sumofChildren = 0;
if(root->left){
sumofChildren+=root->left->data;
}
if(root->right){
sumofChildren+=root->right->data;
}
if(sumofChildrendata){
if(root->left){
root->left->data=root->data;
}
if(root->right){
root->right->data=root->data;
}
}else{
root->data=sumofChildren;
}
// go left then go right
reorder(root->left);
reorder(root->right);
// while coming back
int total = 0;
if(root->left){
total+=root->left->data;
}
if(root->right){
total+=root->right->data;
}
// just check if any one of left or right exists
if(root->left || root->right){
root->data=total;
}
}
Level Order Traversal can solve it as well and with much better intuition
int isSumProperty(Node *root)
{
queue q;
q.push(root);
while(!q.empty()){
Node* node = q.front();
q.pop();
int left = 0;
int right = 0;
if(node->left){
left+=node->left->data;
q.push(node->left);
}
if(node->right){
right+=node->right->data;
q.push(node->right);
}
if(left+right != 0 && left+right != node->data){
return 0;
}
}
return 1;
}
=> we check left + right != 0 to consider that leaf nodes cannot have a child.
In line 16 of C++ code, i think there should be an 'if' instead of 'else if'. Or am i missing something ?? Someone please clarify.
I just checked, and the code works fine for both 'if' and 'else if'. How is this making sense ? Someone please explain 🙏🙏
@@jatinchoubey6053 we reassign the values to left and right children because we want the sum to be greater than the root node. Hence, striver assigned both the children values to the root node only. We can also just assign any one of the children values to root value as the sum of this child's value and the other child's value (which is always positive) will anyways be greater than the root node
Understood
Really helped a lot, thanks a lot
Bhaiya if root value is less than sum of children then we don't need to change the value of node(line 13). I am right Or not??
You can or you cannot. Same hi h
@@takeUforward okk bhaiya
line 13 is not required
correct
line no.- 16 it will be if and not else if i guess🙄🙄
Yes, I agree