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 5&4 OR 4&9 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>
--
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.
