Lowest Common Ancestor in Binary Tree | C++ Placement Course | Lecture 27.15
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:
This Man Is Going Crazy Keep It Up 😆 Thanks You So Much For All The Lectures❤️🙏
You are literally doing the lord's work!!
in the lac2 , at " 3 " root->next will be checked and after failing in "or" condition next step ie., left and right trees are called and they return 7,6 are present ,hence in the present 3 function in recurssion stack both leftlca(7) and rightlca(6) got these values so they aren't NULL and as we are present at root whose data is 3(root->data) so return "3" takes place :)
after introduction with trees i really thought of solving govt. exam ques like what is the relation between a and b? and here it is the example of family tree... great lectures!!!!
love this course man but just wanted to inform that this lecture should be above the flattening of binary tree vid
Mudde ki baat to end k 5 min me hui h😂💯
Btw notes are much needed now 🙏🏻
This course is perfect for students who want to visualize the concept, keep in mind to solve questions after watching these videos!
from where'
@@aniketbarapatre7630 LeetCode
Optimized approach is easier than the general one :)
Hlo bro can you tell me where is the notes for all this vedio
In the description there is no link for this lecture . Can you please solve my issue ?
@@sudeepbhagat5027 donno man
my suggestion is write your own notes, that'll be helpful :)
Ok no problem i am creating my own notes but notes which provides by faculty is contained some more question so that why I am asking.
9:11 for loop condition should be:
pc
I wasn't know thank you for letting me know 🙏🏽🙏🏽
Great Explanation!🙌🙌
Keep it up✔
@Apna College In the 2nd optimal code there will be a major mistake that it doesn't handle. The code is looking for either n1 or n2 value in the left or right subtree so it can get one value in both right and left subtree and will return some ans, which is false.
No it is look n1 or n2 in own data , which is far more different than you speaking
Your case will happen only if same value is repeated in both side of a binary tree
In the LCA2 before running LCA2 we must ensure that n1 and n2 are present in the tree. Otherwise it will give wrong answer.
For example if tree is 1->2->3 and n1 = 1 and n2 = 4. It give lca as '1' which is wrong.
It will automatically be handled by base case where we reach root == NULL and it will return NULL
@@anuragpandey3341 no, on the first call itself, root-> data == 1, which then return root itself. Gives answer as 1
Oh, yes, correct.......
@@paragsaini2795 last m condition lga skte h if ans==n1 /n2 return NULL
@@sonalidutta825 oh ya
this was THEEEE bESST xplaination i've seeeen so faar on youtube.....thnxxx
May Allah bless you @ApnaCollegeOfficial..👍🤗🤗🤗thanx for such valuable content
Neha toh rahul ki girlfriend thi pehle... Ab behen😂 . Ghor kalyug😂😂😂
notes kha milenge binary tree ke
In 2nd approach,
if both n1 & n2 does not exist in tree => it returns NULL node.
if either n1 or n2 does not exist in the tree => it returns the existing node (it does not return NULL node)
exactly if we take n1 as 7 and n2 as 8... as 7 is in the tree but 8 is not in the tree it should give output as null but its showing as 7.....plzz can someone explain this..
@@prathamnarwade1637 Actually they forgot to add a constraint that either both nodes are present or no one is present. In gfg they mention it clearly.
Is video ko shortest node ke pehle place karna chaiye tha didi
Such a valuable lecture🤗🤗.
Thank u didi...
All videos are awesome
Code is incorrect for LCA2 ..
How?
@@saumyatiwari4030 before returning root in || operator function...code must tell that both n1 and n2 is present in the tree..
Thank You Ma'am !! for your wonderful Explanantion.
notes kha milenge binary tree ke
In lca2 , If one key is present and the other is absent, then it returns the present key as LCA (Ideally should have returned NULL)
so please make another video on lca2(new version)
so that it will handle all cases
Can you elaborate. I am not able to get what you were trying to say. If you can, can explain with examples.
@@ARYANSHARMA-ph8ss actually second approach has a precondition that "Nodes are present" as an assumption... but she didn't tell in the video about it
@@KADOfficial23 han bro abhi leetcode pe question kara toh second test case main hi phas gya lol.
@@KADOfficial23 we can avoid it tho by adding if(path1.at(i)==path2.at(i) && (i+1==path1.size() || i+1==path2.size())) return path1.at(i);
you can use a "count" variable for that.....which will increment when it finds nodes and if count==2 then u can print LCA or else null
Thanku Didi
1 thing for sure for learnning trees u goota be strong with recursion nd backtracking.
Another way to solve this problem
#include
#include
using namespace std;
class node
{
public:
int data;
node *left;
node *right;
node(int v)
{
data = v;
left = NULL;
right = NULL;
pair ancestor(node *curr, int &x, int y)
{
if (curr == NULL)
{
pair p(false, 0);
return p;
}
pair a = ancestor(curr->left, x, y);
pair b = ancestor(curr->right, x, y);
if (x == -1)
{
pair p(false, 0);
return p;
}
if (curr->data == x )
{
if (a.first == true || b.first == true)
{
coutright->left = new node(6);
root->right->right = new node(7);
int a = 2, b =5;
ancestor(root, a, b);
return 0;
}
Rahul and Neha are not cousins 🤣🤣🤣🤣🤣
U mean Non-Hindu xd
@@anaskaratela7171 lol
Exactly 😂
why we are taking node* lca2 not int lca ?
the code of LCA we did in "the shortest distance between 2 nodes" will it not work here and why ???
It will work just u have change and write -1 and root data
fantastic explanation
😀yahi consistency chahiye
#include
#include
using namespace std;
class Node{
public:
int data;
Node* left;
Node* right;
Node(int val){
data=val;
left=NULL;
right=NULL;
}
};
bool getPath(Node *root, int key, vector &path){
if(root==NULL){
return false;
}
path.push_back(root->data);
if(root->data==key){
return true;
}
if(getPath(root->left, key, path)||getPath(root->right, key, path)){
return true;
}
path.pop_back();
return false;
}
int LCA(Node* root, int n1, int n2){
vector path1, path2;
if(!getPath(root, n1, path1) || !getPath(root, n2, path2)){
return -1;
}
int pc;
for(pc=0; pcdata==n1 || root->data==n2){
return root;
}
Node* leftLCA= LCA2(root->left, n2, n1);
Node* rightLCA=LCA2(root->right, n2, n1);
if(leftLCA && rightLCA){
return root;
}
if(leftLCA!=NULL){
return leftLCA;
}
return rightLCA;
}
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);
root->right->right=new Node(6);
root->right->left->left=new Node(7);
Node *lca=LCA2(root, 7, 6);
cout
Thank you 🙏
rahul aur neha ka relation finally aaj samajh mein aaya hai 😄
do not go for this long answer, below is the most optimal code for finding lca
// find the lca of given two nodes in binary tree using cpp
#include
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int val){
data=val;
left=NULL;
right=NULL;
}
};
node* findlca(node* root,int n1,int n2){
if(root==nullptr){
return nullptr;
}
if(root->data==n1 || root->data==n2) return root;
node *leftlca= findlca(root->left,n1,n2);
node*rightlca= findlca(root->right,n1,n2);
if(leftlca && rightlca){
return root;
}
return (leftlca!=nullptr)?leftlca:rightlca;
};
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);
root->right->right= new node(6);
root->right->left->left = new node(7);
int n1=7;
int n2=6;
node* lca = findlca(root,n1,n2);
if(lca!=nullptr){
cout
Thanks bhaiya🙏🙏🙏
Sir best computers in 30000 rupees ek video bnaaye
Why do you not provided the notes of the lectures??
Why we return distance 1+dl
Node *lca(Node *root, int v1,int v2) {
if (root==NULL) {
return NULL;
}
if (root->data>v1 && root->data>v2) {
return lca(root->left, v1, v2);
}
if (root->datadataright, v1, v2) ;
}
return root;
}
this is esay one!!
Thank you mam
honestly saying i watch only your video and i don't like other guy who also makes video.
Paap ghor Paap
Rahul or neha ko cousin bana kar ghor paap kar diya tumne 🥲
What if [1,2,3,null,null,4,4,6,5].....and n1=6 and n2=5 answer toh galat ayga i guess?
Playlist bohot shi chlri thi..great job done...lekin trees pr aate hi saara naas maar diya....🤦♂️ bs code likh kr read kr rhe ho aur kuch nhi...
Bhai yarr magar rahul to neha ko date kar raha tha backtracking ke time pe😂😂
oops rahul neha are cousins
for(pc = 0 ;pc < path2.size() && path1.size() ; pc++)
this part.
pc < path2.size() && path1.size();
can anyone explain?
we will go up to the minimum path(path1,path2),,,,kyuki uss se aage jayege to already 1 array khatm ho chuka to common milne ke to chance hi khtm ... islye apn 2 condition use kr rhe hai taki ek minimum path wale array ke khtm hote hi condition false ho jaye
hope it will help you...
@@HIMANSHUVERMA-wu1hc not true it will run to the value compared first I tried it out on c++ 14
simple since && is used vlue of pc should be less than both at all times else it will fail.
it is just that pc should be less than path2.size() and also path1.size() simple logic you are traversing to your vector till it's last element..
It is [pc
void path(node *root,int k,vector *v) {
if (root==NULL) {
return;
}
if (root->data==k) {
v->push_back(root->data);
return;
}
vector v1,v2;
path(root->left,k,&v1);
path(root->right,k,&v2);
if (!v1.empty()) {
*v = v1;
v->push_back(root->data);
}
if (!v2.empty()) {
*v = v2;
v->push_back(root->data);
}
}
path dhundne ke liye yeh method use kar sakte haikya
int LCM(node *root,int k1,int k2) {
vector p1,p2;
path(root,k1,&p1);
path(root,k2,&p2);
reversevecto(&p1);
reversevecto(&p2);
int ans=-1,n=min(p1.size(),p2.size());
for (int i=0; i
Twist is....rahul's father's name is rahul ll and grandfather's is rahul l
This is aman dhattarwal supremacy
Every boy is rahul
waise aman bhaiya neha rahul karte, yha dono ko bhai behen bna diya 😂😂🤣
should have taught DFS properly first
what will be the LCA of 1 and 7 PLS tell
1
👍
Just tell java course release date. At least tell if it's gonna air or not sir
@@adityapai5147 like your mom pays to comment:)
Bhai Apna Kaksha channel mein dekho Java with DS Algo ka ek pura playlist diya hua haa. dekhlo waha se ho jaega.
@@garv1177 naya playlist aane wala tha bro toh socha with hand to hand wohi se kar lu
@@youtubekakiddokiddo8404 time lagega Ane mein cp aur coding rounds clear karne mein c++ he madad karega Zyada. Naya Java Ane mein deri hoga. But as you wish Naya aya to acha
@@garv1177 ha mai first year me hi hu abhi. I'll wait till this end sem
Wrost Explaination Till Yet... Ratt ke baithe hai yeh ladki
Rahul and neha cousins 😂
Any One in last year of college??
The family tree hierarchy example is sexist and patriarchal.
Not the right place to discuss this....( *if this was not a sarcasm* )