Re: [algogeeks] Finding youngest common ancestor of two nodes in a binary tree
i think u mean lowest commen ancestor?
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.comwrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
How soon 'not now' becomes 'never'...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
@atul it is not a BST
On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are greater than current node then traverse node-right
2. if both are lesser than current node then traverse node-left
3. else return current node pointer.
Any comments,
Atul
On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi negi.1...@gmail.com wrote:
could you please elucidate more??
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.com wrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
Dear Himanshu,
Here is what I think. This problem can be solved easily by using recursion.
Here is the pseudo code for it:
Logic: Let 'A' and 'B' be the given too node whose common ancestor we have
to find. Now perform an inorder traversal of the tree and at every node call
the 'search(A)' function on the left subtree and search(B) function on the
right subtree. When both the results are true, you can be assured that this
current node is only the first common ancestor of A, and B, since below the
current node, on either tree the other node (A or B) will not exist, and
above the current node, both A and B will exist on 1 side, so again they
will not exist on either side.
Heres d pseudo code:
//this is a normal recursive function to search for a Key node in the tree
rooted at 'root'
bool search(node *root, node *key){
if(root==NULL)
return false;
if(root==key)
return true;
return search(root-left, key) || search(root-right, key);
}
node* getCommonAncestor(node *root, node *A, node *B){
if(root==NULL)
return NULL;
//if A is present in the left subtree and B is present in the right subtree,
then we have found the common ancestor
if(search(root-left, A) search(root-right, B))
return root;
node* left = getCommonAncestor(root-left, A, B);
node* right= getCommonAncestor(root-right, A, B);
if(left !=NULL)
return left;
if(right !=NULL)
return right;
return NULL;
}
Hope this helps you.
Comments welcome
--
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
lkml.himan...@gmail.comwrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
Well Atul, Mind it, its not a Binary Search Tree, its just a Binary Tree. So
this concept of the elements in left sub tree all having the value less than
the current node and similar for the right subtree will not stand here.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 9:49 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are greater than current node then traverse node-right
2. if both are lesser than current node then traverse node-left
3. else return current node pointer.
Any comments,
Atul
On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi negi.1...@gmail.com wrote:
could you please elucidate more??
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.com wrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
yup atul algo is correct
(cur_data - node-right) * ( cur_data- node-left) -1 for ancestors
On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are greater than current node then traverse node-right
2. if both are lesser than current node then traverse node-left
3. else return current node pointer.
Any comments,
Atul
On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi negi.1...@gmail.com wrote:
could you please elucidate more??
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.com wrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
How soon 'not now' becomes 'never'...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
Apologizes .. I miss read the question.
On Thu, Apr 8, 2010 at 12:14 PM, vivek bijlwan viv...@gmail.com wrote:
@atul it is not a BST
On Thu, Apr 8, 2010 at 10:19 AM, atul verma atul.ii...@gmail.com wrote:
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are greater than current node then traverse node-right
2. if both are lesser than current node then traverse node-left
3. else return current node pointer.
Any comments,
Atul
On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi negi.1...@gmail.com wrote:
could you please elucidate more??
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.com wrote:
For a given binary tree, given the root and two node pointers, how can
we find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
--
Atul Verma
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
could you please elucidate more??
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.comwrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Finding youngest common ancestor of two nodes in a binary tree
Its very simple to solve this.
Start from root.
Compare the value of current node data value to both nodes.
1. if both are greater than current node then traverse node-right
2. if both are lesser than current node then traverse node-left
3. else return current node pointer.
Any comments,
Atul
On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi negi.1...@gmail.com wrote:
could you please elucidate more??
On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
lkml.himan...@gmail.com wrote:
For a given binary tree, given the root and two node pointers, how can we
find their youngest common ancestor.
Say the node is like:
struct node{
int data;
struct node*left, *right;
};
i.e the father field is not there.
Please note that it is not a binary search tree, but just a binary tree.
Thanks,
Himanshu
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
