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

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches