 Lowest common ancestor

The lowest common ancestor of two vertices is the common ancestor farthest from the root. In the ancestor partial order with the root least, it is their infimum, also called their greatest common ancestor.

The lowest common ancestor (LCA) of two nodes in a tree is defined as the deepest node that is an ancestor of both nodes. In a more formal sense, if you have two nodes \( p \) and \( q \) in a tree, the LCA is the node \( x \) such that: 1. \( x \) is an ancestor of both \( p \) and \( q \).