**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:**