finding the Lowest Common Ancestor in a general tree having the parent Ids

Question

My roblem is to find the LCA for a general tree that would be created from a list in a txt file. I am looking for the most efficient implementation. The data is in the form of: Id, info, ParentId

The data is not sorted in any way. I was thinking about creating a tree, but that would take at least O (nlogn). Although the log base is not 2. It depends on the avg number of children I suppose.

Instead, if I store the nodes in hashtable, then finding LCA would be better than O (nlogn). Right? For each parent of the destination node, I have to chwck whether it has been visited by the source node or not (assume that we start from source node up to the root and mark all the parent on the way as visited), which takes O (logn). Since, we just check the parents, it would be better than O(nlogn).

Any better idea?

Answer 1

Suppose your tree is somehow balanced, I.e. O(logn) height, your hashtable data structure should give a O(n) algorithm.

First trace from both source and destination to root. You will have two paths of length O(logn). E.g. SXYZR and DWYZR. S and D are source and destination. R is the root. This takes O(logn) time.

Then you can find the longest postfix which is YZR. Y will be the LCA. This takes O(logn) time.

Remember you need O(n) time to read input and build hashtable.