[Solved]: LCA from children using bottom up approach?

Problem Detail: 

I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom up without using depth.

How would I go about traversing the tree, starting from any 2 arbitrary nodes, each of which points to a previous node as shown without a depth variable?

Asked By : ujvl

Answered By : Yuval Filmus

Here is one approach. Given leaves $\alpha,\beta$, first compute the depths $d(\alpha),d(\beta)$ of both leaves (to compute the depth of a leaf, measure how many times you need to apply the parent operation until you reach the root). Suppose without loss of generality that $d(\alpha) \geq d(\beta)$. Replace $\alpha$ with $\alpha$'s $(d(\alpha) - d(\beta))$'th parent. The least common ancestor doesn't change, and so we can assume without loss of generality that $\alpha$ and $\beta$ are at the same depth.

If $\alpha = \beta$, then $\alpha$ is the least common ancestor. Otherwise, replace both $\alpha$ and $\beta$ with their parents. This doesn't change the least common ancestor. Continue like that, and eventually you will find the least common ancestor.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41088

3.2K people like this

 Download Related Notes/Documents