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.
