lowest common ancestor - How to find the LCA of all pair of nodes in a binary tree

Question

There are some algorithms to find the LCA of a given pair of nodes. But is there any algorithm to find the LCA of all pair of nodes in a binary tree in asymptotic time of less than O(n^2)?

I'm specifically looking for an algorithm with a time span of O(n log n)

Answer 1

You need to think about this problem recursively. Consider the root r of a tree. The LCA of the immediate left chil of r and all of the nodes belonging to the subtree rooted at the immediate right children of r. Do similarly for the immediate right child of r and all the nodes belonging to the tree rooted at the immediate left child of r.

So, let's define a function called LCA as follows (in Pseudo code):

LCA(r)
    if r does not have both a right and left child
        return empty list.
    else
        p1 = pairs made up of left child and all the nodes rooted at right child.
        p2 = pairs made up of right child and all the nodes rooted at the left child.
        p3 = LCA(left child of r)
        p4 = LCA(right child of r)
        return p1 + p2 + p3 + p4