Amazon Interview Question

least common ancestor

Interview Answers

Anonymous

Apr 24, 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

May 10, 2011

@Anonymous: that works only if it is a BST

Anonymous

Apr 15, 2011

it is a binary tree question