Find the Least Common Ancestor of Two Tree Nodes

Problem: Given two nodes in a tree, find the least common ancestor of them.

Solution: This is not a difficult problem. If there is parent pointer, things will be easier. However, simple solution still exist for tree nodes without parent pointer. See the code below:

node * common_ancestor(node *root, node *n1, node *n2)
{
   if(root==null || n1 == null || n2 == null)
     return null;

    if(n1 == root || n2 == root) return root;
   
   node * left = common_ancestor(root->left, n1, n2);
   node * right = common_ancestor(root->right, n1, n2);
   
   if(left && right) return root;
   
   return left ? left : right; 

}

More: if we need to do many common_ancestor() operations, there is a more efficient off-line algorithm called "Tarjan's off-line least common ancestors algorithm". It can get the least common ancestors for m pairs of nodes in just one tree traversal. The main idea is to leverage disjointed forest  with path compression and union by rank.