Max Sum Path from One Node to Another in Binary Tree | C++ Placement Course | Lecture 27.16
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:
![PURPEECH - นี่ฉันเองคนที่... (It's me) [Official MV]](http://i.ytimg.com/vi/NuhHd0hOOg8/mqdefault.jpg)
great explanation mam, the dry run of the code really helps a lot!!
Really doing great job falling in love with the channel ❤️❤️❤️👍
I am in serious need of explanations of recursion like this 🥺it was best.
why are we considering max path through left + maxpath through right + node val in case 4 .............in case 3 hmne to condition le li thi na left child + node val ki
phir 4th case me vhi condition q??
@@sdexstarlord Suppose u have a BT as root=5, left of root=7, right of root=9.
So here, val=5 @root
Left+val=12
Right+val=14
Left+val+Right=21
And max of all these = 21
So, 21 will be our answer
@@doodle7703 but in code she is returning max(root->data, max(left, right)+root->data) then how can 21 be answer if it is root-data + right+ left
for the whole tree we consider the maximum of all 4 (rootdata,rootdata+left,rootdata+right,rootdata+left+right) and for the root's subtrees we try to find a maximum sum path by considering max of (nodedata,nodedata+left,nodedata+right),from these subtrees left and right are given for calculation to the node tree.
Beautiful Explanation Mam❤️, Respect ++
where the value of singlepathsum goes after returning from func (backtrack) does it go on left or right variable or where??
I am not a college student but i appreciate your effort aman bhaiya and team
Hats off for the explanation...... after explanation it was very easy to write the code.
aman bhaiya thanks (hats off)
int maxPathsum(node* root){
if(root==NULL){
return 0;
}
int ans = INT_MIN;
int a=root->data;
int b=maxPathsum(root->left)+root->data;
int c=maxPathsum(root->right)+root->data;
int d=maxPathsum(root->left)+maxPathsum(root->right)+root->data;
int temp=max(max(a, b), max(c, d));
ans=max(ans, temp);
return ans;
}
This works as well...
Can someone explain me why is the second value (node value + right + left) I mean I understand about the other 3 values but what exactly is the logic behind ( node value + right + left)
Always waiting for the new lesson
Gajab❤️
Aman bhaiya please make video on startup fund raising
Recently you talked in tedx video
then what is use of ans in masutil function
I also have doubt in this part Why she calculated ans when there is no need of it
In maxPathUtil function pass ans as a ( & ) reference insted of pass by value
: ) Happy coding
if we put +6 in place of -6 in the example tree
then the ans will be 15 according to the program
but the ans should be 10
i think the problem is because we include nodeval + leftmax + right max
Answer should be 14 na ?? (6+3+5)
her approach seems wrong to me
we included it in max variable not in return value
#include
using namespace std;
struct Node {
int data;
struct Node*left;
struct Node*right;
Node(int val){
data=val;
left =NULL;
right=NULL;
}
};
int maxPathsum(Node* root){
if(root==NULL){
return 0;
}
int ans = INT_MIN;
int a=root->data;
int b=maxPathsum(root->left)+root->data;
int c=maxPathsum(root->right)+root->data;
int d=maxPathsum(root->left)+maxPathsum(root->right)+root->data;
int temp=max(max(a, b), max(c, d));
ans=max(ans, temp);
return ans;
}
int main()
{
struct Node* root = new Node(1);
root->left = new Node(-2);
root->right = new Node(4);
root->left->left = new Node(4);
root->right->right = new Node(-5);
cout
This Man Is Going Crazy Keep It Up 😆 Thanks You So Much For All The Lectures❤️🙏
Sister is there any efficient way of inserting elements into binary tree ,if there plz provide the code for inserting elements into binary tree dynamically
There is a way... In these videos there is a VIdeo on Build a Binary Tree from Preorder. You have to give array of elements which you want to insert in Preorder and Inorder. And then just call the function buildtree and it will build a tree for you. Hope this clears your doubt.
if feels like just finishing the topic anyway .
Bhot hard😥🔥🔥
Thank you 🙏🙏
really nice video
In maxPathSumUtil why we calculated ans if we have to return the value of singlePathSum????
I don't get why we have calculated single path sum
Same doubt and in ans there is whole path traversal but in single path there is no whole path traversal
Ans is calculated for whole path traversal and no need to return ans because it is stored in address of variable so it gets changed automatically
cause it only updates the ans and the function made to return values only at a specific node's right or left ,right and left of a node may be included but its not necessary that it is included
Yaa
Even if we do that to modify and,it won't as it is not send as pointers but the function take the values not variables in consideration.
why ans variable is used if return is of singlepathsum variable?????
exactly
That is beacuse we are calculating maxpathsum between any two nodes of the tree and not just the root and leaf node.
Waiting for android studio
Me also
Aman bhaiya please make video on startup fund raising
Recently you talked in tedx video
Initially music is good , but when teaching starts it becomes irritating . I advise you to turn it off .
true, it distracts us understanding the starting explanation. Have to watch it 2-3 times in beginning to understand
Maximum path mein Root to leaf node tak ki calculation must hai, I mean to say is if here root 1 ki jagah -1 hota toh value 8 hoti ya phr 7?
#include
#include
using namespace std;
class Node{
public:
int data;
Node* left;
Node* right;
Node(int val){
data=val;
left=NULL;
right=NULL;
}
};
int maxPathSumUntil(Node* root, int &ans){
if(root==NULL){
return 0;
}
int left=maxPathSumUntil(root->left, ans);
int right=maxPathSumUntil(root->right, ans);
int nodeMax=max(max(root->data, root->data+left+right), max(root->data+left, root->data+right));
ans=max(ans, nodeMax);
int singlePsum=max(root->data, max(root->data+left, root->data+right));
return singlePsum;
}
int maxPathSum(Node* root){
int ans=INT_MIN;
maxPathSumUntil(root, ans);
return ans;
}
int main(){
Node* root=new Node(1);
root->left=new Node(2);
root->right=new Node(3);
root->left->left=new Node(4);
root->right->right=new Node(5);
cout
very poor sound quality!!
Kya koi senior bata sakta hei ye c++ ka course kaisa hei?
Kya mujhe is channel se seekhna chaiye ya kisi aur channel se??
course to achha hai pr ye kab tak khatam hoga ye nahi pata .
maine coding isi course se start ki thi uske baad me gfg aur coding ninja ka course se kr raha hu
@@vikasmane8851 bhai coding ninjas ke course ke baare mai bata sakte ho ki like kesa structure hai unka
Yess, you can follow this course without any single doubt, I'm also revising my DSA concepts by this playlist.
@@pranavverma5291 concept explain karte hai aur questions karate hai
like ye apna college ke jaisa hi hai course but coding ninja wale thoda jyada explain karte hai aur logic ko boht jyada explain karte hai
@@vikasmane8851 Bro coding ninja ke course ka price kitna hai bro please reply
Is there any difference between Node* root and Node *root?
no
nope
Na
no, but the correct syntax is Node *root
Basically you rae making pointer of type Node. So if you are making multiple then you need to add * in front of all pointer variable. Eg: Node *root1, *root2;
Eg: Node* root1, *root2;
Both above examples are correct;
But Node* root1, root2; is not correct.
please share notes 🙏🙏🙏
// code in video
#include
#include
using namespace std;
struct Node{
int data;
Node *left, *right;
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};
int maxPathAumUtil(Node *root, int &ans){
if(root == NULL){
return 0;
}
int left = maxPathAumUtil(root -> left, ans);
int right= maxPathAumUtil(root -> right, ans);
int nodeMax = max(max(root->data, root->data + left + right),
max(root->data+ left, root->data + right));
ans = max(ans, nodeMax);
int singlePathsum = max(root->data, max(root->data + left, root -> data + right));
return singlePathsum;
}
int maxPathSum(Node *root){
int ans = INT_MIN;
maxPathAumUtil(root, ans);
return ans;
}
int main()
{
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
// test
cout
Please notes public krdo 🥲
Bhaut dikkat ho rhi hai without practice questions 😢
plz help!
Que samjh nhi ayya
Max distance from root nikalna h ya max distance left + max dis right nikalna from root nikalna h?
Max possible sum (sum of value at node) nikalna hai whether it is of just left subtree or right subtree or both including ancestor.
Code is right but initial explanation was wrong
💖💖💖💖💖💖💖💖💖💖
If we do +12 instead of -12 then, why it is giving 25 instead of 17 🧐🧐
Coz the path in that case will be
4-> 12 -> 1 -> 3 -> 5
,which adds to give 25
@@shikhamaurya4453 thanks got it 👍👍
Can you first try to explain the intuition behind the approach instead of jumping directly to the approach?
Didi samajh nahi aaya bahut comolex ho gaya hai yeh problem ab tak kisimein bhi itni takleef nahi huu
Yaar koi ye meko samajyega .......apan ye single path sum kyu nikal rahe
Haa mujhe bhi...
Why am I geting lowest possible value?
Ya same..
Can anyone explain me why we have calculate single path sum because we are not storing its value in any variable .
we r returning single path because either left of the node or right of the node will be part of the max sum path not both if both r returned then path wil have branches which we dont want
@@learningoverflow3138 So why are we taking that possibility in the first place? Why do we not take something like
ans = max(root->data+left, root->data+right);
ans = max(ans, root->data);
@@ARYANSHARMA-ph8ss no ans is max of all the four quantities left,right,left+right,node->data
u might be confused between the util function and the actual answer
the ans is sum of whole path right
but the util function just decides what branch of the tree should be part of the path
@@learningoverflow3138 Yes and I am not able to understand how can left+right both can be the branch path. If you can explain me that would be awesome :)
@@ARYANSHARMA-ph8ss yea it cannot be unless its the topmost node
but while checking the answer in util function we have to check whether the node we r currently at has sum(that is basically checking should the node be added to the current path or should it be the topmost node) greater then the previous node
hope u have understood it !
ask if u have doubt
i dont know why but this is giving lowest integer value
store the answer returned by utility function in a variable, and then print max of ans and that variable
@@anujmaurya2786 thanks just tried it's working now
Please someone explain why this code is not working for negative numbers?
int maxPathsum(Node* root){
if(root==NULL) return 0;
int val = INT_MIN;
val = root->data;
int leftSubtree = maxPathsum(root->left);
int rightSubtree = maxPathsum(root->right);
val +=max(leftSubtree,rightSubtree);
return val;
}