First Common Ancestor of a Binary Tree

Question

If I have a binary search tree like this then what will be lowest common ancestor of nodes 6 and 1?

Binary Search tree

it is a test case to test whether the algorithm is running properly — Madu, Apr 12 '12 at 23:44
`8` would be the answer in this case - but I have seen people answering `6` as well — BrokenGlass, Apr 13 '12 at 00:31
is people answering 6 in the similar case or is there any difference in that case. Can you tell me the exact answer? — Madu, Apr 13 '12 at 00:34

score 4 · Accepted Answer · answered Apr 13 '12 at 00:44

According to the Wikipedia definition of the Lowest common ancestor I correct myself:

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

So yes going by this definition the correct answer would be 6. If this is an interview question would be good to clarify in advance with the interviewer.

First Common Ancestor of a Binary Tree

1 Answers1

Linked

Related