To find least common ancestor in a binary search tree

Question

Ryan · Accepted Answer

1) find the right most node of the left child of the node in question.
 2) if no right child of the left node, the left node itself is your answer.
3 if neither of the above two are available traverse back to the firs ancestor who value is the node in queston's value.

Ella · Answer

Have a recursive method with the root and the two values were trying to find the LCA for in the parameter.
Because this is a binary search tree we know that the LCA will be the node where value 1 is less than and where value 2 is greater than. So you will return the root when the the case stated above is true. And then two statements after will either go to the left or right child depending on if the values are both greater than or less than.

Ryan · Answer

1) find the right most node of the left child of the node in question.
 2) if no right child of the left node, the left node itself is your answer.
3 if neither of the above two are available traverse back to the firs ancestor who value is less than the node in queston's value.

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas