find LCA for two nodes of a binary tree.

Question

Keith · Accepted Answer

I think there's an easier solution:

List1: the parents of node1 in order bottom to top (can get them by navigating up tree from node 1).
Navigate up tree from node2.  First parent of node 2 found in list1 is LCA.

ts · Answer

List 1:  tree nodes inorder
List 2:  tree nodes postorder
List 3:  all the nodes in between the given 2 nodes
List 4:  all the nodes after the given 2 nodes
the LCA is the common node in List 3 and List 4.

fkl · Answer

The advantage? Well complexity is log (n) and there is no extra memory required i.e. no list creation needed

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas