Amazon interview question

least common ancestor

Interview Answers

Anonymous

24 Apr 2011

Traverse down the tree as you would if you were searching the two elements normally. Eventually you will encounter a split decision where you want to do two out of these three possible actions (1) stay at node (i.e., found one of the values), (2) go left, (3) go right. This node is your answer. Assumption is that the tree contains both values.

Anonymous

10 May 2011

@Anonymous: that works only if it is a BST

Anonymous

15 Apr 2011

it is a binary tree question