Lowest common ancestor

The lowest common ancestor (LCA) of two nodes is the lowest node that has both nodes as descendants. The algorithm works by tracing the path from the first node to the root of the tree using parent pointers. The path from the second node is then traced upward until the first intersection with the path from the first node. This node is the lowest common ancestor. The first path is stored in a set such that insertion and test have $O(1)$ cost.

The time and space complexity of this algorithm is $O(h)$ where $h$ is the height of the tree. This is $O(\log n)$ for balanced trees.