We can optimize the code using DP...
On Wed, Jun 15, 2011 at 8:24 PM, immanuel kingston <
[email protected]> wrote:
> The following is for LCA for 2 nodes in a n-ary tree.
>
> A more tougher problem is to find the LCA for n nodes in the same n-ary
> tree.
>
> Node * findLCA (Node *root, Node * l, Node * r, int n) {
> if (l == null || r == null) return root;
> if (root == null) return null;
> if (isChild(root,l) || isChild(root, r)) {
> return root;
> }
> Node * arr[n];
> int count = 0;
> Node * notNull;
> for (int i = 0 ; i < n ; i ++ ) {
> arr[i] = findLCA(root->children[i], l, r);
> if ( arr[i] != null ) {
> count ++; notNull = arr[i];
> }
> }
> if (count == 0) {
> return null;
> } else if (count == 2) {
> return root;
> } else {
> return notNull;
>
> }
> }
>
> On Wed, Jun 15, 2011 at 2:59 PM, Piyush Sinha <[email protected]>wrote:
>
>> WAP to find the LCA in a n-ary tree.
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/profile.php?id=100000655377926 *
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks and Regards,
------------------------------
*DIPANKAR DUTTA*
Visiting Research Scholar
Dept of Computing,
Macquarie University, Sydney, Australia
ph.no-+61 2 98509079 ( Mon-Fri 10:15-7:00) Sydney time
email: [email protected]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
