Problem description:
Design an algorithm for computing the LCA of two nodes in a binary tree. The algorithm’s time complexity should depend only on the distance from the nodes to the LCA.
Hint: Focus on the extreme case described in the problem introduction.
Solution:
Intuitively, the brute-force approach si suboptimal because it potentially processes nodes well above the LCA. We can avoid this by alternating moving upwards from the two nodes and storing the nodes visited as we move up in a hash table. Each time we visit a node we check to see if it has been visited before.
Reference:
