Re: [algogeeks] LCA of a Binary tree not a binary search tree
@anshu
I was just replying to the earlier comments not to ur post.
On Tue, Nov 22, 2011 at 2:23 PM, abhishek kumar wrote:
> If you maintain the parent, it'll be a simple problem.
> Just go to the two nodes and then trace their parents till you reach the
> common node.
>
>
> On Tue, Nov 22, 2011 at 1:59 PM, anshu mishra
> wrote:
>
>> first try to understand the sol then comment. it is for binary tree not
>> for BST.
>>
>> On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover <
>> piyush4u.iit...@gmail.com> wrote:
>>
>>> For BST it would be rather simpler. find the first node which lies in
>>> between the two.
>>>
>>> On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra >> > wrote:
>>>
Node *LCA(node *root, node *e1, node *e2, int &x)
{
Node *temp =NULL;
Int y = 0;
If (root->left) temp = LCA(root->left, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
y = 0;
If (root->right) temp = LCA(root->right, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
If (root == e1 || root == e2) x++;
Return null;
}
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Anshuman Mishra | Software Development Engineer | Amazon
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards
> *Abhishek*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
If you maintain the parent, it'll be a simple problem.
Just go to the two nodes and then trace their parents till you reach the
common node.
On Tue, Nov 22, 2011 at 1:59 PM, anshu mishra wrote:
> first try to understand the sol then comment. it is for binary tree not
> for BST.
>
> On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover > wrote:
>
>> For BST it would be rather simpler. find the first node which lies in
>> between the two.
>>
>> On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra
>> wrote:
>>
>>> Node *LCA(node *root, node *e1, node *e2, int &x)
>>>
>>> {
>>>
>>> Node *temp =NULL;
>>>
>>> Int y = 0;
>>>
>>> If (root->left) temp = LCA(root->left, e1, e2, y);
>>>
>>> x+=y;
>>>
>>> if (temp) return temp;
>>>
>>>if (x==2) return node;
>>>
>>> y = 0;
>>>
>>> If (root->right) temp = LCA(root->right, e1, e2, y);
>>>
>>> x+=y;
>>>
>>> if (temp) return temp;
>>>
>>> if (x==2) return node;
>>>
>>> If (root == e1 || root == e2) x++;
>>>
>>> Return null;
>>>
>>> }
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Anshuman Mishra | Software Development Engineer | Amazon
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Regards
*Abhishek*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
first try to understand the sol then comment. it is for binary tree not for
BST.
On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover
wrote:
> For BST it would be rather simpler. find the first node which lies in
> between the two.
>
> On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra
> wrote:
>
>> Node *LCA(node *root, node *e1, node *e2, int &x)
>>
>> {
>>
>> Node *temp =NULL;
>>
>> Int y = 0;
>>
>> If (root->left) temp = LCA(root->left, e1, e2, y);
>>
>> x+=y;
>>
>> if (temp) return temp;
>>
>>if (x==2) return node;
>>
>> y = 0;
>>
>> If (root->right) temp = LCA(root->right, e1, e2, y);
>>
>> x+=y;
>>
>> if (temp) return temp;
>>
>> if (x==2) return node;
>>
>> If (root == e1 || root == e2) x++;
>>
>> Return null;
>>
>> }
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
For BST it would be rather simpler. find the first node which lies in
between the two.
On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra wrote:
> Node *LCA(node *root, node *e1, node *e2, int &x)
>
> {
>
> Node *temp =NULL;
>
> Int y = 0;
>
> If (root->left) temp = LCA(root->left, e1, e2, y);
>
> x+=y;
>
> if (temp) return temp;
>
>if (x==2) return node;
>
> y = 0;
>
> If (root->right) temp = LCA(root->right, e1, e2, y);
>
> x+=y;
>
> if (temp) return temp;
>
> if (x==2) return node;
>
> If (root == e1 || root == e2) x++;
>
> Return null;
>
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
Node *LCA(node *root, node *e1, node *e2, int &x)
{
Node *temp =NULL;
Int y = 0;
If (root->left) temp = LCA(root->left, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
y = 0;
If (root->right) temp = LCA(root->right, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
If (root == e1 || root == e2) x++;
Return null;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
Yeah, right. the same algo of binary tree can be used for bst also but using that is expensive. On Mon, Nov 14, 2011 at 9:56 PM, AMAN AGARWAL wrote: > Hi, > > I think it matters whether its a bst or normal tree. In BST left node is > smaller and the right node is greater than the root node, but no such > constraint is applicable for a binary tree. > > Regards, > Aman. > > > On Mon, Nov 14, 2011 at 10:12 AM, sumit mahamuni < > sumit143smail...@gmail.com> wrote: > >> Hi, >> >> >> On Mon, Nov 14, 2011 at 1:52 AM, AMAN AGARWAL wrote: >> >>> >>> Hi, >>> >>> Please tell me the solution of this question. >>> >>> write a program which find LCA of a binary tree. It is not a BST >>> >> Does it matter its a BST or binary tree? the algo will be same for the >> BST or binary tree. >> >> >>> >>> Regards, >>> Aman, >>> >>> -- >>> AMAN AGARWAL >>> "Success is not final, Failure is not fatal: It is the courage to >>> continue that counts!" >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks and Regards, >> Sumit Mahamuni. >> >> -- Slow code that scales better can be faster than fast code that >> doesn't scale! >> -- Tough times never lasts, but tough people do. >> -- I love deadlines. I like the whooshing sound they make as they fly >> by. - D. Adams >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > AMAN AGARWAL > "Success is not final, Failure is not fatal: It is the courage to continue > that counts!" > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks and Regards, Sumit Mahamuni. -- Slow code that scales better can be faster than fast code that doesn't scale! -- Tough times never lasts, but tough people do. -- I love deadlines. I like the whooshing sound they make as they fly by. - D. Adams -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
Hi, I think it matters whether its a bst or normal tree. In BST left node is smaller and the right node is greater than the root node, but no such constraint is applicable for a binary tree. Regards, Aman. On Mon, Nov 14, 2011 at 10:12 AM, sumit mahamuni wrote: > Hi, > > > On Mon, Nov 14, 2011 at 1:52 AM, AMAN AGARWAL wrote: > >> >> Hi, >> >> Please tell me the solution of this question. >> >> write a program which find LCA of a binary tree. It is not a BST >> > Does it matter its a BST or binary tree? the algo will be same for the BST > or binary tree. > > >> >> Regards, >> Aman, >> >> -- >> AMAN AGARWAL >> "Success is not final, Failure is not fatal: It is the courage to >> continue that counts!" >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks and Regards, > Sumit Mahamuni. > > -- Slow code that scales better can be faster than fast code that doesn't > scale! > -- Tough times never lasts, but tough people do. > -- I love deadlines. I like the whooshing sound they make as they fly by. > - D. Adams > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- AMAN AGARWAL "Success is not final, Failure is not fatal: It is the courage to continue that counts!" -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* lca(struct node* root,struct node* a,struct node* b){
if(!root) return NULL;
if( root==a || root ==b) return root;
struct node* left = lca(root->left,a,b);
struct node* right = lca(root->right,a,b);
if( left && right) return root;
return (left ? left : right);
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
Hi, On Mon, Nov 14, 2011 at 1:52 AM, AMAN AGARWAL wrote: > > Hi, > > Please tell me the solution of this question. > > write a program which find LCA of a binary tree. It is not a BST > Does it matter its a BST or binary tree? the algo will be same for the BST or binary tree. > > Regards, > Aman, > -- > AMAN AGARWAL > "Success is not final, Failure is not fatal: It is the courage to continue > that counts!" > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks and Regards, Sumit Mahamuni. -- Slow code that scales better can be faster than fast code that doesn't scale! -- Tough times never lasts, but tough people do. -- I love deadlines. I like the whooshing sound they make as they fly by. - D. Adams -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] LCA of a Binary tree not a binary search tree
Hi, Please tell me the solution of this question. write a program which find LCA of a binary tree. It is not a BST Regards, Aman, -- AMAN AGARWAL "Success is not final, Failure is not fatal: It is the courage to continue that counts!" -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
