Hi,

I agree 90% with the solution to this problem. However, it is not explicit what the answer would be for the LCA of nodes with value 12 and 14 in the picture. The implementation suggested would place 12 as the solution.

It seems 8 would be a more fitting LCA, so I stored the previousNode for each iteration. If the two are not both greater or both less than, then I check for if the currentNode is A or B. If so, then use previousNode (convergence). Otherwise currentNode is LCA(divergence).

Thoughts?

Erich

It all hinges on what you consider to be the definition of "ancestor". If a node is an ancestor of itself (which is what the definition in the book implies) then the book's assertion is correct. If you say that a node cannot be its own ancestor, then your assertion is correct.

But if a node is not an ancestor of itself, you'll have problems dealing with finding the LCA of any set of nodes that includes the root node....

Eric

The point I wanted to make was that in an interview you should make it clear what you mean by "ancestor". In your scenario, for example, returning null would make the most sense for any set of nodes that included the root node. But the interviewer might be confused unless you told them what your interpretation of "ancestor" was.

Eric

that's an excellent point! i did not consider a pair of nodes including the root node.... should have saw that edge case :P thanks for the reply!

No problem, and thanks for the question!

Eric