**This is an old revision of the document!**

The lowest common ancestor (LCA) of two nodes is the lowest node that has both nodes as node descendants. The algorithm works by tracing the path from the first node to the route of the tree using `parent`

pointers. The path from the second node is 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.

lowest_common_ancestor.1422746644.txt.gz · Last modified: 2015/02/02 08:24 (external edit)