Lowest 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 \).