Re: [algogeeks] Re: Closest ancestor of two nodes
this solution works if parent pointer is given.
1. Start moving up from both the nodes (if two nodes become equal, fine this
is the common ancestor) till you reach the root node and in between count
the number of nodes you covered in their path for both the nodes. Say 7 for
node A and 10 for node B.
2. Now from B (longer path node) move up 3 (10-7) nodes.
3. now start moving up from B's new position and from A. Wherever they meet
is the common ancestor.
On Sat, Sep 3, 2011 at 11:13 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
For BST it is easy ...it can be find in O(logn) time ..
when ever we find that the direction we are searching for x and y are
different, that node is the common ancestor ...no need to find either x or y
where the nodes are...
what about binary tree ? how do we search an element in binary tree
efficiently ?
On Sat, Sep 3, 2011 at 12:44 AM, rajul jain rajuljain...@gmail.comwrote:
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.comwrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail
if one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in
right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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.
[algogeeks] Re: Closest ancestor of two nodes
DON's solution will work
On Sep 3, 11:28 am, Abhishek Yadav algowithabhis...@gmail.com wrote:
this solution works if parent pointer is given.
1. Start moving up from both the nodes (if two nodes become equal, fine this
is the common ancestor) till you reach the root node and in between count
the number of nodes you covered in their path for both the nodes. Say 7 for
node A and 10 for node B.
2. Now from B (longer path node) move up 3 (10-7) nodes.
3. now start moving up from B's new position and from A. Wherever they meet
is the common ancestor.
On Sat, Sep 3, 2011 at 11:13 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
For BST it is easy ...it can be find in O(logn) time ..
when ever we find that the direction we are searching for x and y are
different, that node is the common ancestor ...no need to find either x or y
where the nodes are...
what about binary tree ? how do we search an element in binary tree
efficiently ?
On Sat, Sep 3, 2011 at 12:44 AM, rajul jain rajuljain...@gmail.comwrote:
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.comwrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail
if one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2); // check recursively in
right subtree
if(ltree!=null rtree!=null) // One node in left another in
right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in the
following tree:
3
\
4
/ \
5 8
/
9
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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] Re: Closest ancestor of two nodes
it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
num_stack1=find the first element using in order (pushing the ancestor of
the first element) in first stack.
num_stack2=find the second element using in order (pushing the ancestor of
the second element) in second stack.
num_stack1=num_stack2=num_stack1num_stack2?num_stack1:num_stack2;
while(stack1[num_stack1--]!=stack2[num_stack2--]);
return (stack1[num_stack1])
Thank you,
Sid.
On Sat, Sep 3, 2011 at 6:05 PM, vikas vikas.rastogi2...@gmail.com wrote:
DON's solution will work
On Sep 3, 11:28 am, Abhishek Yadav algowithabhis...@gmail.com wrote:
this solution works if parent pointer is given.
1. Start moving up from both the nodes (if two nodes become equal, fine
this
is the common ancestor) till you reach the root node and in between count
the number of nodes you covered in their path for both the nodes. Say 7
for
node A and 10 for node B.
2. Now from B (longer path node) move up 3 (10-7) nodes.
3. now start moving up from B's new position and from A. Wherever they
meet
is the common ancestor.
On Sat, Sep 3, 2011 at 11:13 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
For BST it is easy ...it can be find in O(logn) time ..
when ever we find that the direction we are searching for x and y are
different, that node is the common ancestor ...no need to find either x
or y
where the nodes are...
what about binary tree ? how do we search an element in binary tree
efficiently ?
On Sat, Sep 3, 2011 at 12:44 AM, rajul jain rajuljain...@gmail.com
wrote:
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.com
wrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will
fail
if one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2
) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 ||
root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in
left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in
right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in
the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
Re: [algogeeks] Re: Closest ancestor of two nodes
it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
//find the first element using in order
{
stack1[num_stack1++]=(pushing the ancestor of the first element) in first
stack.
}
//find the second element using in order
stack2[num_stack2++]= (pushing the ancestor of the second element) in second
stack.
num_stack1=num_stack2=num_stack1num_stack2?num_stack1:num_stack2;
while(stack1[num_stack1--]!=stack2[num_stack2--]);
return (stack1[num_stack1])
Thank you,
Sid.
Thank you,
Sid.
On Sat, Sep 3, 2011 at 7:25 PM, siddharam suresh siddharam@gmail.comwrote:
it can done in with 2 stack(size/length of the each stack is hieght of the
tree),(stack1,stack2)
num_stack1=find the first element using in order (pushing the ancestor of
the first element) in first stack.
num_stack2=find the second element using in order (pushing the ancestor of
the second element) in second stack.
num_stack1=num_stack2=num_stack1num_stack2?num_stack1:num_stack2;
while(stack1[num_stack1--]!=stack2[num_stack2--]);
return (stack1[num_stack1])
Thank you,
Sid.
On Sat, Sep 3, 2011 at 6:05 PM, vikas vikas.rastogi2...@gmail.com wrote:
DON's solution will work
On Sep 3, 11:28 am, Abhishek Yadav algowithabhis...@gmail.com wrote:
this solution works if parent pointer is given.
1. Start moving up from both the nodes (if two nodes become equal, fine
this
is the common ancestor) till you reach the root node and in between
count
the number of nodes you covered in their path for both the nodes. Say 7
for
node A and 10 for node B.
2. Now from B (longer path node) move up 3 (10-7) nodes.
3. now start moving up from B's new position and from A. Wherever they
meet
is the common ancestor.
On Sat, Sep 3, 2011 at 11:13 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
For BST it is easy ...it can be find in O(logn) time ..
when ever we find that the direction we are searching for x and y are
different, that node is the common ancestor ...no need to find either
x or y
where the nodes are...
what about binary tree ? how do we search an element in binary tree
efficiently ?
On Sat, Sep 3, 2011 at 12:44 AM, rajul jain rajuljain...@gmail.com
wrote:
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.com
wrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com
wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will
fail
if one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2
) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 ||
root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in
left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in
right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in
the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
--
You received this message
Re: [algogeeks] Re: Closest ancestor of two nodes
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.com wrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail
if one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
--
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] Re: Closest ancestor of two nodes
For BST it is easy ...it can be find in O(logn) time ..
when ever we find that the direction we are searching for x and y are
different, that node is the common ancestor ...no need to find either x or y
where the nodes are...
what about binary tree ? how do we search an element in binary tree
efficiently ?
On Sat, Sep 3, 2011 at 12:44 AM, rajul jain rajuljain...@gmail.com wrote:
@anika this solution only works for BST
On Mon, Aug 15, 2011 at 4:20 PM, Anika Jain anika.jai...@gmail.comwrote:
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail
if one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in
right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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] Re: Closest ancestor of two nodes
node *common_ancestor(node *root, node **prev, int x,int y)
{
if(root-a==x || root-a==y)
return *prev;
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-l,prev, x,y);
}
else if(root-a x root-a y)
{
prev=root;
return common_ancestor(root-r,prev, x,y);
}
else
{
prev=root;
return *prev;
}
}
with call as
node *prev=NULL;
common_ancestor(root,prev,x,y);
On Sun, Aug 14, 2011 at 10:08 PM, Yasir yasir@gmail.com wrote:
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail if
one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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.
[algogeeks] Re: Closest ancestor of two nodes
Check the c language implementation:
node* LeastCommonAncestor(const node* root, const int data1, const int
data2, int* const status){
static node* ans = NULL;
int l_st=0, r_st=0;
if(root==NULL) return;
if(root-left != NULL)
LeastCommonAncestor(root-left, data1, data2, l_st);
if(root-right != NULL)
LeastCommonAncestor(root-right, data1, data2, r_st);
if(l_st == 3 || r_st == 3)//if both data already found by subtrees
return ans;
if((l_st|r_st)==3){//if one data found in each subtree
*status = 3;
ans=root;
return ans;
}
if( ((l_st|r_st)==2 root-data == data1) || ((l_st|r_st)==1
root-data == data2) ){
//if one data found in subtree and other is root itself
ans = root;
*status =3;}
else//record if any one data found (case when both data found is
catered above)
*status |= l_st |= r_st;
if(root-data == data1)
*status |= 1;
if(root-data == data2)
*status |= 2;
return ans;
}
Full Program here:
https://github.com/monish001/CPP-Programs/blob/master/General/LeastCommonAncestor.c
Program tested on Dev-CPP
-
Monish
On Aug 9, 7:56 pm, Raman raman.u...@gmail.com wrote:
Can anyone give me the recursive algo to find closest ancestor of two nodes
in a tree(not a BST).
--
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] Re: Closest ancestor of two nodes
Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail if
one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2);// check recursively in
right subtree
if(ltree!=null rtree!=null)// One node in left another in right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 54 OR 49 would be 3 in the
following tree:
3
\
4
/\
5 8
/
9
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
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] Re: Closest ancestor of two nodes
Don solution is perfect.
i double checked it..
On Aug 9, 9:01 pm, Don dondod...@gmail.com wrote:
tree closestSharedAncestor(tree root, tree node1, tree node2, int
result)
{
tree returnValue = 0;
if (root)
{
if (root == node1) result += 1;
if (root == node2) result += 2;
int sum = 0;
tree returnLeft = closestSharedAncestor(root-left, node1, node2,
sum);
if (returnLeft) returnValuet = returnLeft;
else
{
tree returnRight = closestSharedAncestor(root-right, node1,
node2, sum);
if (returnRight) returnValue = returnRight;
else if (sum == 3) returnValue = root;
}
result += sum;
}
return returnValue;
}
On Aug 9, 9:56 am, Raman raman.u...@gmail.com wrote:
Can anyone give me the recursive algo to find closest ancestor of two nodes
in a tree(not a BST).- Hide quoted text -
- Show quoted text -
--
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] Re: Closest ancestor of two nodes
tree closestSharedAncestor(tree root, tree node1, tree node2, int
result)
{
tree returnValue = 0;
if (root)
{
if (root == node1) result += 1;
if (root == node2) result += 2;
int sum = 0;
tree returnLeft = closestSharedAncestor(root-left, node1, node2,
sum);
if (returnLeft) returnValuet = returnLeft;
else
{
tree returnRight = closestSharedAncestor(root-right, node1,
node2, sum);
if (returnRight) returnValue = returnRight;
else if (sum == 3) returnValue = root;
}
result += sum;
}
return returnValue;
}
On Aug 9, 9:56 am, Raman raman.u...@gmail.com wrote:
Can anyone give me the recursive algo to find closest ancestor of two nodes
in a tree(not a BST).
--
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.
