User Tools

Site Tools

This is an old revision of the document!

Lowest common ancestor

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

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